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);
    }

}
  • 时间复杂度:O(n) 每个节点只遍历了⼀次
  • 空间复杂度:O(logn) 算上递推系统栈的空间

Q.E.D.


以无限为有限,以无法为有法