LeetCode 337. 打家劫舍 III

约 5 分钟
文章信息 12 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 20-50 腾讯 字节 微软 亚马逊 美团 快手 图森
标签
动态规划 深度优先搜索 树 二叉树

题目描述

✅ 337. 打家劫舍 III

image-20260928203653923

image-20260928203653924

题意分析

每个树节点代表一间房屋，节点值是其中的钱。直接相连的父子房屋不能同时偷，求一晚能够取得的最大金额。

限制只针对父子之间，不限制不同分支，也不限制祖父与孙子。允许不偷根节点，不能简单规定只偷某一层或全部隔层节点，而要根据各子树的金额选择。

解法：树形动态规划

核心思路

[!blue]

父节点是否被偷，只会直接影响孩子根节点能否被偷。因此，每棵子树向父节点返回两个最优值就足够：notRob 表示不偷当前根时，整棵子树最多能偷多少；rob 表示偷当前根时，整棵子树最多能偷多少。它们都包含子孙的收益，并非只考虑当前节点。

若偷当前节点，它的两个孩子就都不能偷，但更深处仍按各自最优安排。因此 rob = node.val + left[0] + right[0]，其中下标 0 表示孩子根不偷的状态。

若不偷当前节点，两个孩子就各自可以偷或不偷。左右子树之间没有相连的节点，选择互不干扰，所以分别取最优值再相加：notRob = max(left[0], left[1]) + max(right[0], right[1])。

这两个状态覆盖了当前根偷与不偷的所有可能，而子树内部的最优选择已由孩子状态给出。因此按后序先算孩子、再算父节点，就能自底向上得到最优解。空子树两种收益均为零；整棵树没有父节点施加限制，答案取根的两个状态中的较大值。

解题步骤

  1. 定义递归返回值 [notRob, rob]，空节点返回两个零。
  2. 递归计算左右子树，得到它们的两种状态。
  3. 偷当前节点时，累加当前金额以及两个孩子根不偷的收益。
  4. 不偷当前节点时，左右子树分别取两种状态的最大值，再相加。
  5. 返回当前子树的二元状态；在主函数中返回根状态的最大值。

代码实现

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)$。

关键点总结

[!green]

  • 状态必须区分当前根是否被偷，因为父节点要据此限制孩子的选择。
  • 不偷当前节点，只解除它对孩子的限制，不代表放弃整棵子树。
  • 左右子树相互独立，才能在给定当前根状态后分别最优化再求和。
  • 一次递归返回两种收益，避免分开递归孩子、孙子造成重复计算。

易错点总结

[!yellow]

  • 偷当前节点时，不能再取孩子两种状态的最大值，否则可能同时偷父子；此时只能取孩子的 notRob。
  • 不偷当前节点时，不能强迫孩子也不偷，应让左右孩子各自选择收益更大的状态。
  • 不能按层号统一选择奇数层或偶数层，最优选择可能在不同分支中采用不同安排。
  • 两种状态的下标含义必须一致；最终也不能强制选根，应返回两种状态的最大值。
  • 只返回一个“子树最大收益”会丢掉根是否被偷的信息，父节点无法正确判断能否与它同时选择。

相似题目

题目 难度 关联与区别
198. 打家劫舍 中等 把相邻房屋不能同时选择推广为树上父子不能同时选择，需要为每个子树保存选与不选两种收益。
213. 打家劫舍 II 中等 比较选择当前元素与跳过当前元素的最优值；本题树上分别返回选根与不选根的结果，该题拆开环形首尾冲突的两种情况。
740. 删除并获得点数 中等 比较选择当前元素与跳过当前元素的最优值；本题树上分别返回选根与不选根的结果，该题按值累计收益后禁止选择相邻值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/99943604
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！