LeetCode 337. 打家劫舍 III

约 5 分钟
文章信息 12 个分类 6 个标签
分类
LeetCode CodeTop 中等 已解决 20-50 字节跳动 微软 美团 快手 腾讯 亚马逊 图森
标签
动态规划 深度优先搜索 树 二叉树 树形 DP 打家劫舍问题
目录

题目描述

✅ 337. 打家劫舍 III

image-20250419000557407

image-20250419000609853

题意分析

输入是一棵二叉树，每个节点上放着一笔钱，要求选出一个节点集合使得金额之和最大。唯一的限制是：如果一个节点被选中，它的直接父节点和直接子节点都不能被选中，也就是被选中的节点之间不能存在父子边。

约束里有两个信号值得留意。其一，节点数量在万级，说明允许的做法只能是把整棵树扫一遍量级的，不能对每个节点再重新遍历它的子树。其二，节点金额非负，所以「多选一个不相邻的节点」永远不会让答案变差，不必担心出现「主动放弃一笔钱反而更优」这种反直觉情况。

边界上要考虑：树只有一个节点时答案就是这个节点的值；某个节点只有单侧孩子甚至没有孩子时，缺失的一侧必须按「收益为 0」参与合并，而不是被跳过。答案只问最大金额，不需要还原具体选了哪些房子。

解法：树形动态规划

核心思路

直接枚举每个节点偷或不偷有指数级组合；若“偷当前节点”时再递归四个孙子，也会反复计算同一子树。父节点其实只需要知道子树的两种结果：子树根不偷时的最优值，以及子树根被偷时的最优值。

定义 dfs(node) 返回 [notRob, rob]：

  • notRob：确定不偷 node 时，这棵子树的最大收益；
  • rob：确定偷 node 时，这棵子树的最大收益。

后序计算左右子树。若偷当前节点，两个孩子都不能偷：rob = node.val + left.notRob + right.notRob；若不偷当前节点，两个孩子可独立选择更优状态：notRob = max(left) + max(right)。空节点返回 [0, 0]。

正确性可按树高归纳：叶子显然返回 [0, value]；假设左右子树的两个状态都最优，上述转移枚举了当前节点“偷”和“不偷”的全部合法情况，并为每棵子树选择对应最优值，因此当前子树的两个状态也最优。根节点没有父节点限制，取两种状态的较大值即可。

解题步骤

  1. 对空节点返回 [0, 0]，让缺失孩子自然以收益 0 参与转移。
  2. 后序递归左右孩子，分别得到它们“根不偷 / 根偷”的最优收益。
  3. 偷当前节点：累加当前金额和左右孩子的“不偷”状态。
  4. 不偷当前节点：左右孩子各自在两种状态中取最大值，再相加。
  5. 返回当前节点的二元状态；最终对根节点的两个状态取最大值。

例如 [3,2,3,null,3,null,1]：左子树返回 [3,2]，右子树返回 [1,3]。根不偷为 max(3,2) + max(1,3) = 6，根偷为 3 + 3 + 1 = 7，答案是 7。

代码实现

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

    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }

        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int notRob = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);
        int rob = node.val + left[0] + right[0];
        return new int[]{notRob, rob};
    }
}

func rob(root *TreeNode) int {
    state := robTree(root)
    return maxInt(state[0], state[1])
}

func robTree(node *TreeNode) [2]int {
    if node == nil {
        return [2]int{}
    }

    left := robTree(node.Left)
    right := robTree(node.Right)
    notRob := maxInt(left[0], left[1]) + maxInt(right[0], right[1])
    robCurrent := node.Val + left[0] + right[0]
    return [2]int{notRob, robCurrent}
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(n)$。每个节点只被后序访问一次，节点内只进行常数次运算。
  • 空间复杂度：$O(h)$，其中 $h$ 为树高，来自递归栈；平衡树为 $O(\log n)$，链状树为 $O(n)$。

关键点总结

  • 树形 DP 的状态必须包含“当前节点是否选择”，因为这正是子树对父节点产生影响的唯一信息。
  • 偷当前节点时孩子只能取受限的“不偷”状态；不偷当前节点时孩子才可自由取最大值。
  • 一次递归同时返回两个状态，避免为了访问孙子而重复计算子树。
  • 面试中先给出状态语义，再写转移式；只写 [0]、[1] 而不解释含义，很容易把两支写反。

易错点总结

  • 偷当前节点时不能写 node.val + max(left) + max(right)。例如 [3,4,5] 会得到非法的 12，而正确答案是孩子之和 9。
  • 不偷当前节点不代表孩子也不能偷；若写成 left[0] + right[0]，[1,2,3] 会错误地得到 0 而不是 5。
  • 最终答案必须是根的两种状态取最大值，不能强制偷根或强制不偷根。
  • 递归顺序必须是后序，因为父节点的状态依赖左右子树已经计算出的状态。
  • 朴素地递归孩子和孙子会产生重复子问题；若返回值只有“子树最大值”，说明状态信息不够。

相似题目

题目 难度 考察点
198. 打家劫舍 中等 线性数组上的相邻不可选，一维滚动状态
213. 打家劫舍 II 中等 首尾相接成环，拆成两段线性问题各跑一次
740. 删除并获得点数 中等 先按数值桶计权重，把选数问题转化为相邻不可选
LCR 089. 打家劫舍 中等 198 同题，用于练习状态压缩成两个变量
LCR 090. 打家劫舍 II 中等 213 同题，重点在环形边界的两种切分方式
面试题 17.16. 按摩师 简单 相同模型的入门版，只需最基础的两状态递推