题目链接：337. 打家劫舍 III - 力扣（LeetCode）
前情提要：
本体是打家劫舍的一个变形题，希望大家能先做198. 打家劫舍 - 力扣（LeetCode），并看一下我上题的讲解力扣198-打家劫舍（Java详细题解）-CSDN博客，再看本题会觉得好一点。
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。
题目思路:
本题是将二叉树和dp结合的一道题目，刚开始做这种题目的朋友可能会很懵，普通的dp我会呀，但是结合二叉树就不知道怎么入手了。
没关系，我带大家梳理一下思路。
既然是二叉树类的题目，那么难免要进行二叉树的遍历。
本题二叉树遍历是哪一种？
由题目描述可以看出，每一个节点就是一间房间，俩个相邻的房间不能同时偷。
意思就是俩个相连的节点就不能偷，再深入点就是当前节点如果已经偷了，那么他的子节点是不能偷的，如果当前节点不偷，那么他的左右孩子是可以考虑偷的。
所以该题是用后序遍历的，我们要根据他的左右孩子节点的状态来推出他父节点的状态。
该题也与打家劫舍1和2的状态一样，每个节点都有俩种状态，选或不选。
所以每一层我们就用dp数组来表示我们的状态，dp[0] 表示不偷本节点的子树结构的最高金额,dp [1] 表示偷本节点的子树结构的最高金额。
肯定会有人疑问，dp数组怎么就记录每个节点的偷窃状态，那我其他节点的怎么处理。其实这就是我们要用后序遍历的一个好处了，后序遍历可以优先处理左右孩子节点的情况，然后将左右孩子节点的返回值返回给中间节点处理。
意思就是本层的递归值中就有我孩子节点的状态，我可以用我孩子节点的状态来推出我本层节点的状态。
可能这里大家看起来有点懵，后序看代码就清晰很多了。
接下来我们用动规五部曲来系统分析一下。
1.确定dp数组和i下标的含义。
dp[0] 就是以该节点为“根节点”的树结构不考虑偷所得的最大金额。
dp[1] 就是以该节点为“根节点”的树结构考虑偷所得的最大金额。
2.确定递推公式。
本层节点不偷，那我就可以考虑我左右孩子节点偷。
注意我这里都是考虑，都不一定非要偷，偷不偷不是我决定的，而是递推公式找出最大值来确定偷不偷。
dp[0] = Math.max(left[0],lefr[1]) + Math.max（right[0],right[1]);
这里的left[]其实就是我左孩子节点的dp状态数组，right就是我右孩子节点的dp状态数组。我左右孩子分别考虑偷或不偷，取一个最大即可。
所以这里就可以看出我们只用给每一个节点设立dp数组就可以，左右孩子节点可以由递归返回值得出。
本层节点偷，那我左右孩子节点肯定就不能偷了对吧。
那我就将本层节点的值和左右孩子不能偷的最大金额加上即可。
dp[1] = root.val + left[0] + right[0];
3.dp初始化。
其实本题的初始化就是给那些空节点进行初始化。因为是后序遍历，回溯时需要从后往前推。
那么递归碰到空节点时就会停止，从而回溯往前推，所以递推的初始值就是空节点的值。
空节点初始化为什么呢？想想dp数组的定义。我当前节点都为空了 我偷不偷都会0。所以初始化为{0,0}
4.确定dp的遍历顺序。
这里就不说dp的遍历顺序，还是二叉树的遍历顺序，因为是在树结构上进行递推，所以是以树的遍历顺序为主。
本题遍历顺序后序。
5.如果没有ac打印dp数组 利于debug。
最终代码：
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public int rob(TreeNode root) {//面对二叉树问题 我们首先想到的就是遍历顺序 这道题我们是采用前中后序还是层序呢？//该题我们要考虑左右孩子的被打劫的情况再考虑本节点的情况，所以本题要采用后序遍历。//后序遍历的特点就是将左右孩子节点的情况反馈给本节点 然后再做处理.//该题也与前俩个打家劫舍的状态一样，每个节点都有俩种状态，选或不选。//所以每一层我们就用dp数组来表示我们的状态，dp【0】表示不偷本节点的子树结构的最高金额,dp[1]表示偷本节点的子树结构的最高金额//那么肯定有疑问 这个dp数组怎么记录每个节点的状态。这是因为本层的递归返回值中就有你孩子节点的状态，你可以利用你孩子节点状态来推出你本层节点的状态。//当我们把整个树遍历完了后，这棵树的最终结果就在根节点处。int [] result = robTree(root);return Math.max(result[0],result[1]);}public int[] robTree(TreeNode root){//定义dp数组int dp[] = new int[2];if(root == null)return dp;//遍历顺序 左 右 中int[] left = robTree(root.left);int[] right = robTree(root.right);//不偷本节点的状态//那我就要考虑我的左右孩子节点是否要偷dp[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);//偷本节点的状态//我的左右孩子节点肯定不能偷dp[1] = root.val + left[0] + right[0];//本节点考虑完了往上层返回值return dp;}
}
这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。
我很乐意为你解答。那么我们下篇再见！
