一、与前两个打家劫舍I和打家劫舍II的区别主要区别在怎么偷家1、力扣198.打家劫舍I线性数组2、力扣213.打家劫舍II环形3、力扣337.打家劫舍III树二、思考过程1、因为是树所以要考虑遍历顺序。所以要考虑递归2、因为递归的时候要先知道左右孩子的状态返回给父节点才能判断父节点的状态。所以考虑后续遍历3、因为从下往上左右孩子的状态会影响父节点的状态状态从叶子节点一直移到根节点。所以考虑动态规划所以本题要考虑递归、动态规划、树这三个部分那么就要考虑“递归三部曲”、“动规五部曲”、“树的遍历顺序”这几个关键问题三、关键性问题1、dp数组的含义:在dp数组里定义两个元素数组下标为“0”表示“不偷”当前节点数组下标为“1”表示“偷”当前节点。dp[0]表示“不偷”当前节点的“最大钱币数”dp[1]表示“偷”当前节点的“最大钱币数”dp数组在本题有两个一个是左孩子的dp数组leftdp一个是右孩子的dp数组rightdp。2、递归的终止条件如果在后序遍历的时候遍历到了叶子节点的左右孩子也就是空节点就是终止条件。假设此时遍历到叶子节点的左孩子就返回vectorint{0,0}表示的意思是不偷叶子节点的左孩子的最大钱币数为0偷叶子节点的左孩子的最大钱币数为03、递推关系i)不偷当前节点数组下标为0当前节点的最大钱币数为dp[0] 左孩子不偷或偷的最大钱币数 右孩子不偷或偷的最大钱币数也就是dp[0] max(leftdp[0],leftdp[1]) max(rightdp[0],rightdp[1])ii)偷当前节点数组下标为1当前节点的最大钱币数为dp[1] 当前节点的钱币数 左孩子不偷的最大钱币数 右孩子不偷的最大钱币数 因为相邻节点不能同时偷所以要这样设置也就是dp[1] cur-val leftdp[0] rightdp[0]【下图以力扣上的题目的示例1作推理】