337. 打家劫舍 III

难度: 中等
来源: 每日一题 2023.09.18

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 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
/**
 * 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) {

    }
}

分析与题解

  • 动态规划 + 层序遍历 结果: 思路失败, GG

    这个题目我一开始考虑到的是利用二叉树的层序遍历, 把每一次层的金钱数遍历出来, 但是发现其实上思路是错误的. 因为我们要遵循的条件只有 父子节点不能同时被偷!

    为啥这么说呢, 我们看下面的示例图就知道了.

    如果按照层序遍历的解题思路, 我们要想获得最大钱数, 我们只能选择第一层和第三层, 如下图所示. 那么最大收益是 1000 + 10 + 10 + 10 + 10 = 1040

    但是正确的选择是什么呢? 那就是如下图所示, 最终的收益是10 + 1000 + 100 = 1110

    最后还是要把当时的想法解题思路贴出来, 如下所示.

    /**
* 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) {
        if (root == null) {
            return 0;
        }
        // 二叉树的层序遍历, 构建出每层的金额
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        List<Integer> levelMoney = new ArrayList<>();
        while(!deque.isEmpty()) {
            int length = deque.size();
            int level = 0;
            for(int i = 0; i < length; i++) {
                TreeNode node = deque.poll();
                level += node.val;
                if (node.left != null) {deque.add(node.left);}
                if (node.right != null) {deque.add(node.right);}
            }
            levelMoney.add(level);
        }
        int maxRob = levelMoney.get(0);
        int maxNotRob = 0;
        int temp = 0;
        for (int i = 1; i < levelMoney.size(); i++) {
            temp = maxRob;
            maxRob = Math.max(maxNotRob + levelMoney.get(i), maxRob);
            maxNotRob = temp;
        }
        return Math.max(maxNotRob, maxRob);
    }
}

    结果如下所示.

    结果: 思路失败, GG


  • 动态规划 + 深度优先遍历 结果: 成功

    在先前一次考虑了很久, 也是没有啥思路, 所以就看官方题解了, 我们知道我们唯一需要遵循的条件就是 父子节点不能同时被偷!

    那么, 我们需要还是动态规划的思想, 一个节点只能有偷与不偷的两种选择, 要求某一个节点的获取金币数量最大化, 我们可以分情况讨论.

    • 当前节点被偷, 那么最大金币数就是 当前节点金币数 + 左节点不偷时最大金币数 + 右节点不偷时最大金币数

    • 当前节点不被偷, 那么最大金币数就是 左节点不偷时与偷时两者中最大金币数 + 右节点不偷时与偷时两者中最大金币数

    有了以前的状态转移方程思路, 我们首先构建两个HashMap, 用来存储节点选中与不选中时能获取最大金币数.

    Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

    然后进行深度优先遍历, 遍历的过程, 我们就来根据上面我们总结的动态规划思路来构建我们的HashMap.

    public void dfs(TreeNode node) {
    if (node == null) {
        return;
    }
    dfs(node.left);
    dfs(node.right);
    Integer fMoney = node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0);
    f.put(node, fMoney);
    Integer gMoney = Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0));
    g.put(node, gMoney);
}

    当构建完成之后, 我们就取出节点中偷与不偷情况比较出最大值就是我们想要的结果. 这样整体的解题过程就完成了.

    return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));

    整体的解题思路如下所示.

    /**
* 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 {
    Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
    Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        Integer fMoney = node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0);
        f.put(node, fMoney);
        Integer gMoney = Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0));
        g.put(node, gMoney);
    }
}

    复杂度分析:

    • 时间复杂度: O(n), 深度优先遍历需要遍历到每一个节点, 所以递归遍历的次数与节点数量相同.
    • 空间复杂度: O(2n), 开辟需要与节点数量2倍的内存空间.

    结果如下所示.

IT界无底坑洞栋主 欢迎加Q骚扰:676758285