LeetCode 337. 打家劫舍 III

题目描述

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

除了 root 之外，每栋房子有且只有一个“父房子”与之相连。一番侦察之后，聪明的小偷意识到：

如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

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

示例分析

示例 1

输入: root = [3,2,3,null,3,null,1]
输出: 7

这棵树大致是：

一种最优方案是：

偷根节点 3
不偷它的两个孩子 2 和 3
再偷孙子节点 3 和 1

总金额为：

3 + 3 + 1 = 7

示例 2

输入: root = [3,4,5,1,3,null,1]
输出: 9

树结构大致为：

最优方案是：

不偷根节点 3
偷左右孩子 4 和 5

总金额为：

4 + 5 = 9

解题思路

这道题表面上和前面的“打家劫舍”系列很像，但实际上已经从线性数组变成了树形结构。

在线性版本里，我们只需要考虑：

偷当前房子
不偷当前房子

然后用一维 DP 就能解决。

但这道题不一样，因为房子之间的关系不是一条直线，而是一棵树。所以不能直接套前面那种线性状态转移，而要用：

树形 DP + 后序遍历

你给出的代码正是这道题最经典的写法。

代码

class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[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 rob = left[1] + right[1] + node.val; 
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); 
        return new int[]{rob, notRob};
    }
}

这份代码的核心就在于：

对于每个节点，都计算两个状态：

偷当前节点时的最大收益

不偷当前节点时的最大收益

为什么线性 DP 不能直接套过来

前面的打家劫舍 I / II 中，房子是按顺序排列的，所以“相邻不能同时偷”这个约束很容易表达。

但在这题里，“相邻”变成了：

父节点和子节点不能同时偷

这是一种树上的相邻关系，不再是数组上的前后关系。

所以不能再用类似：

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

这种写法。

因为一个节点的最优选择，取决于它左右子树各自的情况。

这就意味着我们要：

先算出左右子树的结果
再合并成当前节点的结果

这正是树形 DP 的典型模式。

树形 DP 的状态定义

对于任意一个节点 node，我们定义返回值：

res[0] = 偷当前节点时，这棵子树能获得的最大收益
res[1] = 不偷当前节点时，这棵子树能获得的最大收益

注意这里的顺序是：

res[0]：rob
res[1]：notRob

这个定义非常关键。

因为一旦当前节点“偷”还是“不偷”确定下来，左右子树的可选方案也就跟着确定了。

当前节点偷与不偷时，左右子树怎么选

情况 1：偷当前节点

如果偷当前节点，那么它的左右孩子都不能偷。

所以：

左子树只能取“不偷左孩子”的最优值
右子树只能取“不偷右孩子”的最优值

于是：

rob = left[1] + right[1] + node.val

这就是代码中的：

int rob = left[1] + right[1] + node.val;

情况 2：不偷当前节点

如果不偷当前节点，那么左右孩子就可以自由选择：

可以偷
也可以不偷

只需要各自取最优即可。

所以：

notRob = max(left[0], left[1]) + max(right[0], right[1])

这就是代码中的：

int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

为什么这是后序遍历

在代码里：

int[] left = dfs(node.left);
int[] right = dfs(node.right);

先递归求左右子树结果，再计算当前节点结果。

这正是后序遍历的特点：

先处理左子树，再处理右子树，最后处理当前节点。

因为当前节点的状态依赖于左右孩子的状态，所以必须先把子树算完。

这也是几乎所有树形 DP 题的共同特征。

代码解析

1. 主函数

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

对整棵树调用一次 dfs(root)，就能得到：

偷根节点时的最优值
不偷根节点时的最优值

最终答案当然取两者较大值。

因为根节点不一定必须偷，也不一定必须不偷，哪种收益更大就取哪种。

2. 递归终止条件

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

如果当前节点为空：

偷它的收益是 0
不偷它的收益也是 0

这是树形 DP 的基本边界。

3. 递归处理左右子树

int[] left = dfs(node.left); 
int[] right = dfs(node.right);

分别拿到左、右子树的两个状态值。

4. 计算偷当前节点的收益

int rob = left[1] + right[1] + node.val;

因为偷当前节点后，左右孩子都不能偷，所以左右子树只能取“不偷”的状态。

5. 计算不偷当前节点的收益

int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

因为当前节点不偷，所以左右孩子各自都可以自由选，取最大值即可。

6. 返回两个状态

return new int[]{rob, notRob};

把当前节点这棵子树的两个最优值返回给父节点。

手动模拟一下

我们用示例 1：

来模拟。

先看叶子节点 3

对于右下角那个 3：

偷它：3
不偷它：0

[3, 0]

再看节点 2

节点 2 的右孩子返回 [3,0]，左孩子为空 [0,0]

偷 2

rob = 左不偷 + 右不偷 + 2
    = 0 + 0 + 2
    = 2

不偷 2

notRob = max(0,0) + max(3,0)
       = 0 + 3
       = 3

所以节点 2 返回：

[2, 3]

再看右边节点 3

它的右孩子是 1，左孩子为空。

叶子节点 1 返回：

[1, 0]

于是当前节点 3：

偷 3

rob = 0 + 0 + 3 = 3

不偷 3

notRob = 0 + max(1,0) = 1

[3, 1]

最后看根节点 3

左子树返回：

[2,3]

右子树返回：

[3,1]

偷根节点

rob = left[1] + right[1] + 3
    = 3 + 1 + 3
    = 7

不偷根节点

notRob = max(2,3) + max(3,1)
       = 3 + 3
       = 6

最终根节点返回：

[7,6]

答案取最大值：

为什么这题不用记忆化搜索也能过

有些同学看到树形递归，会想到记忆化搜索。

这题其实不需要额外记忆化，因为：

每个节点只会被访问一次
每个节点只计算一次自己的两个状态
然后结果直接返回给父节点

整个过程是标准的树形 DP，自底向上合并，不会重复计算同一个节点的状态。

所以时间复杂度本身就是线性的。

和“打家劫舍 I”对比

打家劫舍 I

房子是线性的：

[2,7,9,3,1]

状态通常是按下标转移。

打家劫舍 III

房子变成了树：

        3
       / \
      4   5

状态不再按数组位置转移，而是按树节点转移。

所以这题的本质变化是：

从线性 DP 变成树形 DP。

但核心思想还是一样的：

偷当前节点
不偷当前节点

只是“相邻关系”从数组相邻，变成了树上的父子相邻。

复杂度分析

设二叉树共有 n 个节点。

时间复杂度

O(n)

因为每个节点只会访问一次，每次只做常数时间计算。

空间复杂度

O(h)

其中 h 是树的高度，主要来自递归调用栈。

如果树比较平衡，h = log n
最坏情况下树退化成链表，h = n

这道题为什么经典

这题非常经典，因为它是“树形 DP”最有代表性的入门题之一。

它训练的核心能力包括：

能不能把“偷 / 不偷”设计成节点状态
能不能理解父子之间的约束关系
能不能写出后序遍历式的状态合并
能不能把线性 DP 的思想迁移到树上

所以这题不是单纯的树题，也不是单纯的 DP 题，而是：

树形结构上的动态规划

这是很多高级树题的基础。

总结

这道题的核心可以概括成一句话：

对于每个节点，分别计算“偷它”和“不偷它”两种情况下的最大收益，然后由左右子树状态合并得到当前节点状态。

也就是说：

偷当前节点左右孩子都不能偷
不偷当前节点左右孩子各自自由选择最优

所以状态转移就是：

rob = left[1] + right[1] + node.val
notRob = max(left[0], left[1]) + max(right[0], right[1])

你可以把这题记成一句话：

打家劫舍 III 本质是树形 DP：每个节点都维护“偷”和“不偷”两个状态。

这是一道非常经典、也非常值得反复理解的树形 DP 题。真正吃透这题之后，很多“树上选点”的问题都会容易很多。