力扣337-打家劫舍 III（Java详细题解）

题目链接：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;
    }
}

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。

我很乐意为你解答。那么我们下篇再见！