LeedCode---337. 打家劫舍 III|jiutian的博客

337. 打家劫舍 III

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

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

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

示例一：

1652441428263

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

示例 2:

1652441460711

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

提示：

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

解法一：暴力递归

算法思路：

采用后序遍历进行深度优先搜索，如果偷了当前节点，则其两个孩子节点就不能偷；如果没偷当前节点，则可以考虑其左右孩子要不要偷。

超时优化： 这个递归的过程中其实是有重复计算的，计算了 root 的四个孙子（左右孩子的孩子）为头结点的子树的情况（对应下面代码 16、17 行），又计算了 root 的左右孩子为头结点的子树的情况（对应下面代码 19 行），计算左右孩子的时候其实又把孙子计算了⼀遍。所以可以使用⼀个 map 把计算过的结果保存⼀下，减少递归次数。

代码实现：

class Solution {
    public int rob(TreeNode root) {
        return dfs(root);
    }

    // 备忘录
    HashMap<TreeNode, Integer> map = new HashMap<>();

    public int dfs(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return root.val;
        // 如果当前根节点的结果已存在，直接返回
        if (map.containsKey(root)) return map.get(root);
        // 偷根节点，则需要跳过其左右孩子
        int t1 = root.val;
        if (root.left != null) t1 += dfs(root.left.left) + dfs(root.left.right);
        if (root.right != null) t1 += dfs(root.right.left) + dfs(root.right.right);
        // 不偷根节点，考虑其左右孩子
        int t2 = dfs(root.left) + dfs(root.right);
        // 记录当前根节点的结果
        map.put(root, Math.max(t1, t2));
        return Math.max(t1, t2);
    }

}

时间复杂度：O(n)
空间复杂度：O(logn) 算上递推系统栈的空间

解法二：动态规划

算法思路：

采用动态规划（树形DP），对于每个节点偷与不偷得到的最大金额进行记录，并使用后序遍历深度优先遍历该二叉树。

对于需要记录的状态，可用一个长度为 2 的数组 dp 来记录，dp[0] 表示根节点不偷能获得的最高金额，dp[1] 表示根节点偷能获得的最高金额，并且由于是递归，系统栈会保存每⼀层递归的参数，每次递归返回对应根节点的dp数组，所以数组长度只需要 2 即可。

代码实现：

class Solution {
    public int rob(TreeNode root) { 
        List<Integer> list = dpDfs(root);
        return Math.max(list.get(0), list.get(1));
    }

    // ⻓度为 2 的数组，dp[0]：根节点不偷能获得的最高金额，dp[1]：根节点偷能获得的最高金额
    public List<Integer> dpDfs(TreeNode root) {
        // 根节点为空偷不偷都为 0
        if (root == null) {
            return Arrays.asList(0, 0);
        }
        List<Integer> left = dpDfs(root.left);
        List<Integer> right = dpDfs(root.right);
        // 根节点不偷，则其左子树根结点和右子树根结点可以偷，都选偷或不偷较大的那个
        int t1 = Math.max(left.get(0), left.get(1)) + Math.max(right.get(0), right.get(1));
        // 根节点偷，则其左子树根结点和右子树根结点都不能偷
        int t2 = root.val + left.get(0) + right.get(0);
        return Arrays.asList(t1, t2);
    }

}