打家劫舍Ⅲ

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

树的节点数在 [1, 10^4] 范围内
0 <= Node.val <= 10^4

解题思路

方法—

暴力递归

class Solution {
    public int rob(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null&&root.right==null) return root.val;
        //偷父节点
        int val1 = root.val;
        if(root.left!=null) val1 += rob(root.left.left) + rob(root.left.right);
        if(root.right!=null) val1 += rob(root.right.left) + rob(root.right.right);
        //不偷父节点
        int val2 = rob(root.left) + rob(root.right);
        return Math.max(val1,val2);
    }
}

• 时间复杂度：$O(n^2)$，这个时间复杂度不太标准，也不容易准确化，例如越往下的节点重复计算次数就越多
• 空间复杂度：$O(\log n)$，栈的空间

上述代码会超时，因为在递归过程中孩子会重复计算，root的四个孙子为头节点子树的情况，计算root的左右孩子时又把孙子计算了一遍

方法二

记忆法+递归

可以使用一个map把计算的结果保存，这样计算过的孙子就不会重复计算

class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();
    public int rob(TreeNode root) {
        if(root==null) return 0;
        if(map.containsKey(root)) return map.get(root); //如果map里面有记录直接返回
        //偷父节点
        int val1 = root.val;
        if(root.left!=null) val1 += rob(root.left.left) + rob(root.left.right);
        if(root.right!=null) val1 += rob(root.right.left) + rob(root.right.right);
        //不偷父节点
        int val2 = rob(root.left) + rob(root.right);
        map.put(root, Math.max(val1, val2));
        return map.get(root);
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(\log n)$，栈的空间

方法三

递归+动态规划

树形动态规划，需要在树上进行状态转移

1.确定递归函数的参数和返回值

int[] robAction(TreeNode root)

用一个长度为2的数组记录当前结点偷与不偷的最大金额

下标为0记录不偷该节点的最大金额，下标为1记录偷该节点的最大金额

在递归的过程中，系统栈会保存每一层递归的参数

2.确定终止条件

int res[] = new int[2];
if(root==null){
    return res;
}

即返回一个{0，0}的数组

这也相当于dp数组的初始化

3.确定遍历顺序

采用后序遍历

4.确定单层递归逻辑

int[] left = robAction(root.left);
int[] right = robAction(root.right);
res[0] = Math.max(left[0],left[1]) + Math.max(right[0], right[1]);//不偷该节点
res[1] = root.val + left[0] + right[0]; //偷该节点

如果偷当前节点左右孩子就不能偷

如果不偷该结点，左右孩子可以偷，也可以不偷，选最大的即可

代码

class Solution {
    public int rob(TreeNode root) {
        int[] res = robAction(root);
        return Math.max(res[0], res[1]);
    }

    int[] robAction(TreeNode root){
        int res[] = new int[2];
        if(root==null){
            return res;
        }
        int[] left = robAction(root.left);
        int[] right = robAction(root.right);
        res[0] = Math.max(left[0],left[1]) + Math.max(right[0], right[1]);//不偷该节点，子节点可以偷或者不偷
        res[1] = root.val + left[0] + right[0]; //偷该节点，子节点一定不能偷
        return res;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(\log n)$，栈的空间