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。但如果不选根节点选左右儿子和左儿子的两个儿子总共能拿到 22228。贪心直接翻车。树形结构上的决策具有全局耦合性局部最优不等于全局最优。这也是为什么必须用DP来做——我们需要在遍历整棵树的过程中把每种决策的后果都算清楚然后自底向上地合并。2. 树形DP的状态设计思路2.1 核心洞察每个节点只有两种命运树形DP最关键的一步是定义状态。对于这道题每个节点其实只有两种可能被偷或者不被偷。这个洞察看起来简单但它直接决定了整个解法。因为一旦你确定了某个节点偷不偷它的子节点能做什么就确定了如果当前节点被偷那么两个子节点一定不能被偷如果当前节点不被偷那么两个子节点可以被偷也可以不被偷取最大值就行这就是状态转移的全部逻辑。你会发现它和数组版本的打家劫舍在思想上是完全一致的——数组版本里dp[i]表示「考虑到第 i 个位置时能偷的最大值」然后分「偷第 i 个」和「不偷第 i 个」两种情况讨论。树形版本只是把这个逻辑搬到了树上。2.2 两种状态定义方式具体实现上有两种常见的状态定义方式。方式一返回一个长度为2的数组。res[0]表示不偷当前节点时以当前节点为根的子树能偷到的最大值res[1]表示偷当前节点时的最大值。递归函数返回这个数组父节点根据子节点返回的数组来做决策。方式二用哈希表记录每个节点的状态。用一个MapTreeNode, int[]来存储每个节点的两种状态值递归过程中查表。这种方式在有些场景下更灵活但代码量更大而且这道题每个节点只被访问一次没必要用哈希表。我推荐方式一。原因很简单递归函数的返回值天然就是子问题的最优解用数组返回两种状态父节点拿到之后直接做选择逻辑最干净。而且不需要额外的存储空间空间复杂度就是递归栈的深度。2.3 状态转移方程的推导设当前节点为node左子节点为left右子节点为right。如果偷nodenode被偷所以left和right都不能被偷此时的值 node.val left不偷的最大值 right不偷的最大值如果不偷nodeleft和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 两种写法的对比维度递归写法迭代写法代码长度约10行约25行可读性高逻辑直观中需要理解栈模拟空间开销递归栈 O(h)显式栈 哈希表 O(n)栈溢出风险深树时存在无适用场景绝大多数情况树极深或递归受限环境实际刷题时递归写法足够应对所有测试用例。迭代写法更多是作为一种思维训练帮助你理解递归背后的栈机制。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 常见问题速查表问题现象可能原因排查方法结果偏小不偷当前节点时错误地限制了子节点检查not_rob是否用了max结果偏大偷当前节点时没有限制子节点检查rob是否用了left[0]而非max报空指针未处理空节点在递归开头加if not node: return [0,0]结果不稳定状态数组下标含义搞反用变量名替代下标超时重复计算检查是否有节点被多次访问5.5 一个容易忽略的细节题目中金额是非负整数。这个条件其实有影响如果金额可以是负数那「不偷」可能比「偷」更优转移方程需要调整。但题目保证了非负所以偷当前节点时子节点不偷的值一定是非负的不会出现「偷了反而亏」的情况。不过即使金额非负也不代表贪心可行。前面举的反例已经说明了这一点。非负只是保证了DP的某些性质但不改变问题的本质。6. 树形DP的通用套路与扩展6.1 树形DP的通用框架把这道题的解法抽象一下树形DP的通用框架是这样的定义状态确定每个节点需要维护哪些信息。通常是「选/不选」两种或者更多种状态。确定遍历顺序后序遍历自底向上。设计转移方程根据子节点的状态计算当前节点的状态。确定边界条件空节点或叶子节点的返回值。合并最终结果根节点的状态就是全局最优解。这个框架适用于绝大多数树形DP问题。区别只在于状态的定义和转移方程的复杂度。6.2 扩展到「监控二叉树」LeetCode 968「监控二叉树」是另一个经典的树形DP问题。它要求在每个节点上放摄像头摄像头能覆盖自身、父节点和子节点问最少需要多少个摄像头覆盖整棵树。这道题的状态比打家劫舍更复杂每个节点有三种状态有摄像头、无摄像头但被覆盖、无摄像头且未被覆盖。转移方程也更复杂但核心思想是一样的——自底向上根据子节点状态决定当前节点状态。如果你能把打家劫舍 III 吃透监控二叉树只是状态多了一维而已。6.3 扩展到「树的最大独立集」打家劫舍 III 本质上就是带权树的最大独立集问题。如果每个节点的权值都是1那就是无权树的最大独立集。解法完全一样只是把node.val换成1。这类问题在图论中有广泛的应用比如任务调度、资源分配等场景。树上相邻节点不能同时选这个约束在现实中对应的是「互斥资源」的分配问题。6.4 一个变体环形树如果题目变成「树上的节点构成一个环」那就变成了环形打家劫舍的树形版本。解法需要额外考虑环的断开点通常的做法是枚举第一个节点偷或不偷然后分别做树形DP。这个变体在面试中偶尔会出现思路是「破环成树」。7. 实操中的经验与避坑指南7.1 手写代码时的检查清单在面试或笔试中手写这道题时我建议按以下顺序检查递归终止条件写了吗空节点返回[0, 0]。后序遍历的顺序对吗先递归左右子节点再处理当前节点。not_rob的计算用max了吗子节点可以偷也可以不偷。rob的计算用left[0]和right[0]了吗子节点一定不能偷。最终返回的是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(fnode{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, val0, leftNone, rightNone): 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偷根节点的两个孙子节点3317用例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 吃透了这些问题都是同一套逻辑的不同变体。