树形DP入门：从打家劫舍III到树的最大独立集

1. 从一道题看树形DP的本质

1.1 为什么这道题值得反复琢磨

LeetCode 337「打家劫舍 III」在刷题圈里的地位有点特殊。它不像背包问题那样有明确的模板可套，也不像二分查找那样边界清晰，很多人第一次做的时候会卡在一个很别扭的地方：这棵树上的状态到底该怎么定义？

我见过不少朋友刷完前两代打家劫舍（数组版、环形数组版）之后，看到树形版本直接懵了。数组版本的状态转移很直观，dp[i] = max(dp[i-1], dp[i-2] + nums[i])，一眼就能看懂。但到了树上，父子节点之间的依赖关系变成了树形结构，原本线性的思路一下子被打散了。

这道题真正的价值不在于它本身有多难，而在于它是树形DP的入门标杆。你把这题吃透了，后面遇到「树的最大独立集」「树上染色」「监控二叉树」这类问题，思路是相通的。核心就一句话：在树上做决策时，每个节点的状态需要同时考虑选和不选两种情况，并且把这两种情况作为返回值向上传递。

1.2 题目到底在问什么

先把题意捋清楚。给定一棵二叉树，每个节点上有一个非负整数值代表金额。现在要偷钱，规则是：如果偷了某个节点，那么它的直接父节点和直接子节点都不能偷。问最多能偷多少钱。

这个约束的本质是：被偷的节点集合中，任意两个节点不能相邻。翻译成图论语言，就是在树上求一个最大权独立集。

为什么这个约束会导致问题变复杂？因为在数组中，相邻关系是线性的，你只需要看前一个位置有没有偷。但在树上，一个节点同时和它的父节点、左右子节点都有相邻关系，决策的影响是双向的。你偷了当前节点，不仅影响你能不能偷儿子，还影响你父亲能不能偷你。这种双向依赖就是树形DP要解决的核心矛盾。

1.3 为什么贪心在这里行不通

有人可能会想：是不是可以贪心？比如每次选当前能选的金额最大的节点？

不行。举个很简单的反例。根节点金额是 3，左儿子金额是 2，右儿子金额是 2，左儿子的两个儿子金额各是 2。如果贪心选根节点，那左右儿子都不能选，总共拿到 3。但如果不选根节点，选左右儿子和左儿子的两个儿子，总共能拿到 2+2+2+2=8。贪心直接翻车。

树形结构上的决策具有全局耦合性，局部最优不等于全局最优。这也是为什么必须用DP来做——我们需要在遍历整棵树的过程中，把每种决策的后果都算清楚，然后自底向上地合并。

2. 树形DP的状态设计思路

2.1 核心洞察：每个节点只有两种命运

树形DP最关键的一步是定义状态。对于这道题，每个节点其实只有两种可能：被偷或者不被偷。

这个洞察看起来简单，但它直接决定了整个解法。因为一旦你确定了某个节点偷不偷，它的子节点能做什么就确定了：

• 如果当前节点被偷，那么两个子节点一定不能被偷
• 如果当前节点不被偷，那么两个子节点可以被偷也可以不被偷，取最大值就行

这就是状态转移的全部逻辑。你会发现，它和数组版本的打家劫舍在思想上是完全一致的——数组版本里，dp[i]表示「考虑到第 i 个位置时能偷的最大值」，然后分「偷第 i 个」和「不偷第 i 个」两种情况讨论。树形版本只是把这个逻辑搬到了树上。

2.2 两种状态定义方式

具体实现上，有两种常见的状态定义方式。

方式一：返回一个长度为2的数组。res[0]表示不偷当前节点时，以当前节点为根的子树能偷到的最大值；res[1]表示偷当前节点时的最大值。递归函数返回这个数组，父节点根据子节点返回的数组来做决策。

方式二：用哈希表记录每个节点的状态。用一个Map<TreeNode, int[]>来存储每个节点的两种状态值，递归过程中查表。这种方式在有些场景下更灵活，但代码量更大，而且这道题每个节点只被访问一次，没必要用哈希表。

我推荐方式一。原因很简单：递归函数的返回值天然就是子问题的最优解，用数组返回两种状态，父节点拿到之后直接做选择，逻辑最干净。而且不需要额外的存储空间，空间复杂度就是递归栈的深度。

2.3 状态转移方程的推导

设当前节点为node，左子节点为left，右子节点为right。

如果偷node：

• node被偷，所以left和right都不能被偷
• 此时的值 =node.val + left不偷的最大值 + right不偷的最大值

如果不偷node：

• left和right可以偷也可以不偷，各自取最大值
• 此时的值 =max(left偷, left不偷) + max(right偷, right不偷)

写成公式：

偷node = node.val + left[0] + right[0] 不偷node = max(left[0], left[1]) + max(right[0], right[1])

其中left[0]表示不偷左子节点的最大值，left[1]表示偷左子节点的最大值。

最终返回[不偷node, 偷node]这个数组给上一层。

这个转移方程的美妙之处在于：它把「相邻不能同时偷」这个约束，转化成了「偷当前节点时子节点必须不偷」这个确定性规则。约束被编码进了状态转移里，不需要额外判断。

3. 递归实现的完整拆解

3.1 递归函数的定义与返回值

先明确递归函数的语义。我们定义一个函数dfs(node)，它返回一个长度为2的数组[notRob, rob]：

• notRob：不偷node的情况下，以node为根的子树能获得的最大金额
• rob：偷node的情况下，以node为根的子树能获得的最大金额

这个定义非常重要，因为它决定了递归的边界和转移方式。注意，这里的「以 node 为根的子树」包含了 node 本身以及它的所有后代。

递归的终止条件：当node为空时，返回[0, 0]。空节点偷不偷都是0，这是自然的边界。

3.2 后序遍历的执行顺序

为什么必须用后序遍历？因为父节点的决策依赖于子节点的返回值。你必须先知道左右子节点的情况，才能计算当前节点的状态。这就是典型的自底向上的DP。

后序遍历的顺序是：左子树 → 右子树 → 当前节点。对应到代码里：

left = dfs(node.left) right = dfs(node.right) # 此时 left 和 right 已经包含了各自子树的最优解 not_rob = max(left[0], left[1]) + max(right[0], right[1]) rob = node.val + left[0] + right[0] return [not_rob, rob]

这个顺序不能乱。如果你先处理当前节点再处理子节点，那子节点的信息还没算出来，转移方程根本没法执行。

3.3 完整代码实现

class Solution: def rob(self, root): def dfs(node): if not node: return [0, 0] left = dfs(node.left) right = dfs(node.right) # 不偷当前节点：子节点可偷可不偷，取最大值 not_rob = max(left[0], left[1]) + max(right[0], right[1]) # 偷当前节点：子节点一定不能偷 rob = node.val + left[0] + right[0] return [not_rob, rob] result = dfs(root) return max(result[0], result[1])

代码非常短，但每一行都有明确的含义。dfs函数返回的数组就是当前子树的两种状态，父节点拿到之后直接做选择。

3.4 时间与空间复杂度分析

时间复杂度：每个节点恰好被访问一次，每次访问做常数次操作。所以是O(n)，其中 n 是节点数。

空间复杂度：递归栈的深度等于树的高度。最坏情况下（树退化成链）是O(n)，平均情况下是O(log n)。没有使用额外的数据结构，所以空间开销就是递归栈。

这个复杂度已经是最优了。你不可能在少于 O(n) 的时间内遍历完所有节点，也不可能在少于 O(1) 的额外空间内完成状态转移（不考虑递归栈的话）。

4. 从递归到迭代：另一种思路

4.1 为什么有人想用迭代

递归写起来简洁，但有个隐患：如果树非常深，递归栈可能会溢出。虽然在实际刷题场景中很少遇到这种极端情况，但了解迭代写法对于理解树形DP的本质是有帮助的。

迭代写法的核心思路是：用后序遍历的迭代版本，在访问节点时从哈希表中取出子节点的状态，计算当前节点的状态并存入哈希表。

4.2 迭代版本的实现要点

class Solution: def rob(self, root): if not root: return 0 stack = [root] # 记录每个节点的两种状态 memo = {} visited = set() while stack: node = stack[-1] # 如果子节点还没处理完，先处理子节点 if (node.left and node.left not in visited) or \ (node.right and node.right not in visited): if node.right: stack.append(node.right) if node.left: stack.append(node.left) else: stack.pop() visited.add(node) left = memo.get(node.left, [0, 0]) right = memo.get(node.right, [0, 0]) not_rob = max(left[0], left[1]) + max(right[0], right[1]) rob = node.val + left[0] + right[0] memo[node] = [not_rob, rob] result = memo[root] return max(result[0], result[1])

迭代版本明显更长，而且需要额外的visited集合和memo字典。从工程角度看，递归版本更易读、更易维护。除非有明确的栈溢出风险，否则我一般优先写递归。

4.3 两种写法的对比

实际刷题时，递归写法足够应对所有测试用例。迭代写法更多是作为一种思维训练，帮助你理解递归背后的栈机制。

5. 常见错误与排查实录

5.1 状态定义混淆

最常见的错误是把res[0]和res[1]的含义搞反。有人习惯用res[0]表示偷，res[1]表示不偷，然后在转移时忘了对应关系，导致结果完全错误。

我的建议是：在代码里用变量名而不是下标来区分。比如先算出not_rob和rob，最后返回[not_rob, rob]。这样即使你记不住下标含义，看变量名也不会错。

5.2 忘记处理空节点

空节点的返回值必须是[0, 0]。如果你在递归函数里没有处理node is None的情况，直接访问node.val就会报错。这个边界条件看似简单，但在紧张的手写代码场景下很容易漏掉。

5.3 转移方程写错

有人会把「不偷当前节点」的转移写成max(left[0], left[1]) + max(right[0], right[1])，这没问题。但有人会写成left[0] + right[0]，这就错了——不偷当前节点时，子节点是可以偷的，你应该取子节点的最大值，而不是强制子节点也不偷。

记住这个口诀：偷当前，子必不偷；不偷当前，子随意。

5.4 常见问题速查表

5.5 一个容易忽略的细节

题目中金额是非负整数。这个条件其实有影响：如果金额可以是负数，那「不偷」可能比「偷」更优，转移方程需要调整。但题目保证了非负，所以偷当前节点时，子节点不偷的值一定是非负的，不会出现「偷了反而亏」的情况。

不过即使金额非负，也不代表贪心可行。前面举的反例已经说明了这一点。非负只是保证了DP的某些性质，但不改变问题的本质。

6. 树形DP的通用套路与扩展

6.1 树形DP的通用框架

把这道题的解法抽象一下，树形DP的通用框架是这样的：

1. 定义状态：确定每个节点需要维护哪些信息。通常是「选/不选」两种，或者更多种状态。
2. 确定遍历顺序：后序遍历，自底向上。
3. 设计转移方程：根据子节点的状态，计算当前节点的状态。
4. 确定边界条件：空节点或叶子节点的返回值。
5. 合并最终结果：根节点的状态就是全局最优解。

这个框架适用于绝大多数树形DP问题。区别只在于状态的定义和转移方程的复杂度。

6.2 扩展到「监控二叉树」

LeetCode 968「监控二叉树」是另一个经典的树形DP问题。它要求在每个节点上放摄像头，摄像头能覆盖自身、父节点和子节点，问最少需要多少个摄像头覆盖整棵树。

这道题的状态比打家劫舍更复杂，每个节点有三种状态：有摄像头、无摄像头但被覆盖、无摄像头且未被覆盖。转移方程也更复杂，但核心思想是一样的——自底向上，根据子节点状态决定当前节点状态。

如果你能把打家劫舍 III 吃透，监控二叉树只是状态多了一维而已。

6.3 扩展到「树的最大独立集」

打家劫舍 III 本质上就是带权树的最大独立集问题。如果每个节点的权值都是1，那就是无权树的最大独立集。解法完全一样，只是把node.val换成1。

这类问题在图论中有广泛的应用，比如任务调度、资源分配等场景。树上相邻节点不能同时选，这个约束在现实中对应的是「互斥资源」的分配问题。

6.4 一个变体：环形树

如果题目变成「树上的节点构成一个环」，那就变成了环形打家劫舍的树形版本。解法需要额外考虑环的断开点，通常的做法是枚举第一个节点偷或不偷，然后分别做树形DP。这个变体在面试中偶尔会出现，思路是「破环成树」。

7. 实操中的经验与避坑指南

7.1 手写代码时的检查清单

在面试或笔试中手写这道题时，我建议按以下顺序检查：

1. 递归终止条件写了吗？空节点返回[0, 0]。
2. 后序遍历的顺序对吗？先递归左右子节点，再处理当前节点。
3. not_rob的计算用max了吗？子节点可以偷也可以不偷。
4. rob的计算用left[0]和right[0]了吗？子节点一定不能偷。
5. 最终返回的是max(result[0], result[1])吗？根节点偷不偷都有可能。

这五步检查完，基本不会出错。

7.2 调试技巧

如果结果不对，最快的调试方法是在递归函数里打印当前节点的值和返回的数组。比如：

def dfs(node): if not node: return [0, 0] left = dfs(node.left) right = dfs(node.right) not_rob = max(left[0], left[1]) + max(right[0], right[1]) rob = node.val + left[0] + right[0] print(f"node={node.val}, left={left}, right={right}, return={[not_rob, rob]}") return [not_rob, rob]

打印出来之后，对照转移方程手动验算一遍，很快就能定位问题。

7.3 面试中的表达技巧

如果面试官让你讲思路，不要一上来就写代码。先讲清楚状态定义：「我定义递归函数返回一个长度为2的数组，第一个元素表示不偷当前节点的最大值，第二个元素表示偷当前节点的最大值。」然后讲转移方程，最后讲遍历顺序。

这样面试官能跟上你的思路，即使代码有小问题，也能看出你的思维是清晰的。

7.4 一个反直觉的点

有人会觉得：既然偷了当前节点就不能偷子节点，那是不是应该优先偷金额大的节点？这个直觉是错的。因为一个金额小的节点可能有金额很大的孙子节点，偷它反而能解锁更多选择。

树形DP的精髓就在于全局最优，而不是局部贪心。这也是为什么这道题值得反复练习——它能帮你建立「全局视角」的思维习惯。

7.5 性能优化的小技巧

虽然 O(n) 已经是最优复杂度，但在实际运行中，递归的函数调用开销还是存在的。如果你追求极致性能，可以把递归改成迭代，或者用数组模拟栈。不过在刷题场景下，这些优化通常没必要，除非题目明确要求。

另一个小技巧是：如果树的结构允许，可以用Morris遍历把空间复杂度降到 O(1)。但Morris遍历会破坏树的结构，需要额外恢复，代码复杂度高，不推荐在面试中使用。

8. 从这道题延伸出的思维模型

8.1 状态机思维

树形DP的本质是状态机在树上的传播。每个节点是一个状态机，它根据子节点的状态决定自己的状态，然后把状态传递给父节点。这种思维模型可以推广到很多问题：编译原理中的语法分析、网络协议中的状态转换、游戏AI中的行为树，都是类似的结构。

8.2 分治与DP的结合

树形DP是分治思想和DP思想的结合。分治体现在「把树拆成左右子树分别求解」，DP体现在「子问题的解被复用」。理解这一点，你就能明白为什么树形DP既需要递归（分治），又需要状态记录（DP）。

8.3 约束的编码方式

这道题最值得学习的一点是：如何把约束编码进状态转移。「相邻不能同时偷」这个约束，被转化成了「偷当前节点时子节点必须不偷」这个确定性规则。这种「约束转规则」的技巧在算法设计中非常常见，比如背包问题中的容量约束、图着色问题中的颜色约束，都可以用类似的方式处理。

8.4 自底向上的信息聚合

树形DP的另一个核心是自底向上的信息聚合。每个节点把子节点的信息聚合起来，形成自己的信息，再向上传递。这种模式在分布式系统、MapReduce、线段树等场景中都有体现。理解了这个模式，你就能触类旁通。

9. 完整代码与测试用例

9.1 最终代码

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def rob(self, root): def dfs(node): if not node: return [0, 0] left = dfs(node.left) right = dfs(node.right) not_rob = max(left[0], left[1]) + max(right[0], right[1]) rob = node.val + left[0] + right[0] return [not_rob, rob] result = dfs(root) return max(result[0], result[1])

9.2 测试用例

用例1：简单三层树

3 / \ 2 3 \ \ 3 1

预期结果：7（偷根节点的两个孙子节点，3+3+1=7）

用例2：单节点

5

预期结果：5

用例3：链式树

1 \ 2 \ 3

预期结果：4（偷1和3）

用例4：完全二叉树

4 / \ 1 2 / \ 3 5

预期结果：11（偷4、3、5，或者偷1、2、3、5中的某些组合，需要具体计算）

9.3 验证方法

对于每个测试用例，你可以手动模拟递归过程，画出每个节点的返回值，然后对照最终结果。这个过程虽然繁琐，但对于理解树形DP的执行流程非常有帮助。

10. 写在最后的一些个人体会

这道题我前前后后刷了不下十遍。每次重新做，都会有新的理解。最开始只是背模板，后来慢慢理解了状态定义背后的逻辑，再后来能把它和最大独立集、监控二叉树等问题联系起来。

如果你现在还在纠结这道题的细节，我的建议是：不要急着看答案，先自己画一棵小树，手动模拟一遍递归过程。把每个节点的返回值写出来，看看父节点是怎么根据子节点的返回值做决策的。这个过程比看十遍题解都管用。

另外，树形DP的题目有一个特点：代码短，但思维密度高。你可能五分钟就写完了代码，但花了半小时才想明白为什么这么写。这很正常。算法题的价值不在于代码本身，而在于它训练你的思维方式。

最后分享一个我常用的练习方法：做完一道树形DP之后，试着把状态从两种扩展到三种，看看转移方程会变成什么样。比如给每个节点加一个「被父节点覆盖」的状态，或者加一个「正在被处理」的状态。这种扩展练习能帮你真正掌握树形DP的精髓，而不是停留在背模板的层面。

监控二叉树、树的最大独立集、树上染色、树的最小支配集，这些问题的核心都是「在树上做决策，决策之间有依赖关系」。你把打家劫舍 III 吃透了，这些问题都是同一套逻辑的不同变体。