1. 从一道二叉树题看动态规划的空间降维思路第一次在平台上看到 LC.337 这道题的时候我下意识地把它归类成了树上的遍历题。毕竟题目描述很直白一棵二叉树每个节点上有一个非负整数值代表金额相邻的父子节点不能同时被选中求能偷到的最大金额。看起来像是二叉树的后序遍历加一个简单的贪心判断——父节点选了子节点就不能选那比较一下父子节点的值谁大不就行了如果你也这么想过那说明你和我当初踩进了同一个思维陷阱。这道题的核心难点恰恰在于局部最优不等于全局最优。一个父节点的值可能很小但它下面两个子节点的值加起来远超它这时候放弃父节点、选择两个子节点才是正确决策。更复杂的情况是这个决策会沿着树的层级向上传导影响祖父节点甚至更高层节点的选择。这就是典型的树形动态规划问题也是我认为 LeetCode 上把树和动态规划结合得最巧妙的一道题。这篇文章我会从零开始拆解这道题的完整思考链路。不管你是刚接触动态规划的新手还是已经刷过不少 DP 题但一遇到树形结构就发懵的进阶选手我都会把每一步的推导过程、状态定义的理由、空间优化的技巧、以及我在实际编码中踩过的坑讲清楚。文章会涉及递归设计、状态转移方程的推导、记忆化搜索与递推的对比、以及从二维数组到常数额外空间的优化过程。读完你不仅能拿下这道题更重要的是能建立起一套解决树形 DP 问题的通用思维框架。2. 为什么贪心和普通递归都走不通2.1 贪心策略在树形结构上的失效场景很多人拿到这道题的第一反应是自底向上贪心从叶子节点开始如果选了子节点就不选父节点逐层往上推。这个思路在数组版本的打家劫舍LC.198里是成立的因为数组是一条线性的链相邻元素之间的约束关系非常清晰你只需要维护选当前和不选当前两个状态就能线性推进。但树形结构不一样。树的分支意味着一个节点可能有多个子节点而这些子节点之间是互相独立的——选了左子节点不影响右子节点是否可选。贪心策略在处理父节点值小、两个子节点值之和大这种情况时就会出错。举个具体的例子根节点值为 3左子节点值为 4右子节点值为 5左子节点的左子节点值为 10。贪心如果先比较根节点和它的直接子节点发现 459 3于是放弃根节点选择两个子节点。但此时左子节点被选了它的子节点值为 10就不能选最终结果是 459。而最优解其实是选根节点3加上左子节点的子节点10总共 13。贪心在这里彻底失效。这个反例说明了一个关键问题树形结构中的决策不是孤立的每个节点的选择会通过父子约束关系影响到整条路径上的其他节点。你必须同时考虑选这个节点和不选这个节点两种情况下整棵子树能贡献的最大值然后向上传递。2.2 朴素递归为什么会超时理解了贪心不行之后自然的想法是写一个递归对于每个节点返回两个值——选这个节点时子树的最大值和不选这个节点时子树的最大值。选当前节点时子节点只能不选不选当前节点时子节点可以选也可以不选取较大值。这个递归思路本身是对的但如果你直接写出来不做任何优化时间复杂度会非常高。原因在于对于不选当前节点的情况你需要分别计算子节点选和不选的结果然后取最大值。而子节点在计算自己的结果时又会递归地计算它下面所有节点的两种状态。这就导致同一个节点的状态被重复计算了多次。具体来说对于每个节点它的选和不选两个状态会被它的父节点访问一次被祖父节点间接访问一次被更上层的节点继续间接访问。在最坏情况下比如一条链时间复杂度会退化到指数级别。这就是为什么必须引入记忆化或者自底向上的递推来避免重复计算。这里有一个我在面试中经常问候选人的点你能不能估算一下朴素递归的时间复杂度很多人会说 O(n)但实际上如果不做记忆化每个节点的两个状态会被反复计算复杂度是指数级的。能意识到这一点说明你对递归调用栈和状态复用有真正的理解。3. 树形DP的状态定义与转移方程推导3.1 每个节点需要返回哪两个信息树形 DP 的核心在于状态定义。对于这道题每个节点需要向上层返回的信息其实只有两个选当前节点时以当前节点为根的子树能偷到的最大金额记为selected不选当前节点时以当前节点为根的子树能偷到的最大金额记为notSelected为什么是两个而不是更多因为约束条件只涉及父子相邻关系一个节点的决策只影响它的直接子节点不会跨层影响。所以每个节点只需要把我选了和我没选两种情况下子树的最优解告诉父节点就够了。父节点根据自己选不选来决定从子节点拿哪个值。这个状态定义的精妙之处在于它把整棵树的决策问题分解成了每个节点上的两个子问题而且这两个子问题之间是独立的。你可以分别计算它们最后在根节点处取max(selected, notSelected)就是全局最优解。3.2 状态转移方程的完整推导有了状态定义转移方程就水到渠成了。假设当前节点为node它的左子节点为left右子节点为right。当选择当前节点时由于父子不能同时选左右子节点都不能选。所以selected node.val left.notSelected right.notSelected当不选择当前节点时左右子节点可以选也可以不选各自取最大值即可notSelected max(left.selected, left.notSelected) max(right.selected, right.notSelected)这两个公式就是整道题的核心。你会发现它们非常对称逻辑也很直观。但这里有一个容易忽略的细节空节点怎么处理如果某个子节点不存在它的selected和notSelected都应该是 0。这样在计算时不会影响结果也不需要额外的边界判断。我在第一次写这道题的时候就在空节点处理上犯过错。当时我写了一个判断如果子节点为空就跳过结果导致代码里到处都是if (left ! null)的判断逻辑变得很乱。后来改成让空节点返回[0, 0]代码瞬间清爽了很多。这是一个很小的技巧但在树形 DP 中非常实用。3.3 递归返回值的设计选择关于返回值的设计有两种常见的写法。一种是返回一个长度为 2 的数组[selected, notSelected]另一种是返回一个自定义的类或者用两个变量分别接收。在实际编码中返回数组是最简洁的方式因为 Java、Python、JavaScript 都支持直接返回数组或元组。但这里有一个性能上的考量每次递归调用都创建一个新数组会带来额外的内存分配开销。如果对性能要求很高可以考虑用一个全局的二维数组来存储每个节点的状态避免频繁创建对象。不过对于这道题的数据规模来说直接返回数组完全够用代码可读性也更好。我的建议是在面试中优先写返回数组的版本因为它最直观、最容易解释。如果面试官追问性能优化再讨论用全局数组或者返回自定义结构体的方案。4. 从递归到递推两种实现的完整对比4.1 后序遍历递归的代码实现与注释先来看递归版本的完整实现。核心思路是后序遍历先处理左右子树拿到它们的返回值再计算当前节点的两个状态。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def rob(root): def dfs(node): # 空节点返回 [0, 0]表示选或不选都是 0 if not node: return [0, 0] left dfs(node.left) right dfs(node.right) # 选当前节点子节点都不能选 selected node.val left[1] right[1] # 不选当前节点子节点可以选或不选取最大值 not_selected max(left[0], left[1]) max(right[0], right[1]) return [selected, not_selected] result dfs(root) return max(result[0], result[1])这段代码的时间复杂度是 O(n)因为每个节点只被访问一次。空间复杂度是 O(h)其中 h 是树的高度主要是递归调用栈的开销。对于平衡二叉树h log n对于退化成链的树h n。这里有一个细节值得注意dfs函数返回的数组中索引 0 表示选当前节点索引 1 表示不选当前节点。这个顺序一定要统一否则在计算selected和not_selected时很容易搞混。我在早期写这道题的时候就因为顺序搞反了导致结果完全错误调试了半天才发现是索引写反了。4.2 记忆化搜索的适用场景分析有些朋友可能会想能不能用记忆化搜索来优化答案是这道题不需要记忆化。因为每个节点在递归过程中只会被访问一次不存在重复计算的问题。后序遍历天然保证了每个节点只被处理一次它的两个状态直接返回给父节点使用不会被再次访问。那什么时候树形 DP 需要记忆化呢当同一个节点可能被多条路径访问时比如在 DAG有向无环图上做 DP或者树的结构允许从多个父节点到达同一个子节点时。但在标准的二叉树中每个节点只有一个父节点所以后序遍历一次就够了。这一点其实反映了一个更通用的原则树形 DP 的时间复杂度通常就是 O(n)因为树本身的结构保证了每个节点只被处理一次。如果你发现自己的树形 DP 需要记忆化那大概率是状态定义有问题或者你在重复遍历同一棵子树。4.3 迭代版本的实现思路与取舍递归版本虽然简洁但如果树很深可能会栈溢出。这时候可以考虑用迭代的方式来实现后序遍历。思路是用一个栈来模拟递归过程同时用一个哈希表来存储每个节点的计算结果。def rob_iterative(root): if not root: return 0 stack [root] # 存储每个节点的 [selected, not_selected] memo {} while stack: node stack[-1] # 如果左右子节点都还没处理先压入栈 if node.left and node.left not in memo: stack.append(node.left) elif node.right and node.right not in memo: stack.append(node.right) else: # 左右子节点都已处理可以计算当前节点 stack.pop() left_sel, left_not memo.get(node.left, (0, 0)) right_sel, right_not memo.get(node.right, (0, 0)) selected node.val left_not right_not not_selected max(left_sel, left_not) max(right_sel, right_not) memo[node] (selected, not_selected) return max(memo[root])迭代版本的时间复杂度同样是 O(n)但空间复杂度是 O(n)因为需要额外的哈希表来存储所有节点的状态。相比之下递归版本的空间复杂度是 O(h)在平衡树上更优。所以我的建议是除非树的高度可能达到几万层导致栈溢出否则优先用递归版本。代码更短、更易读、更不容易出错。5. 空间优化的极限从二维状态到常数空间5.1 为什么不需要存储整棵树的状态看到这里你可能已经注意到了递归版本中每个节点只返回两个值给它的父节点父节点用完这两个值之后子节点的状态就不再需要了。这意味着我们不需要一个全局的数组来存储所有节点的状态只需要在递归调用栈中保留当前路径上的状态即可。这就是树形 DP 相对于数组 DP 的一个天然优势数组 DP 通常需要一个 O(n) 的 DP 数组来存储所有位置的状态而树形 DP 的状态是沿着树的结构向上传递的处理完一个子树后它的状态就可以被丢弃了。所以空间复杂度自然就是 O(h)而不是 O(n)。5.2 返回值复用的实现细节在实际编码中这个状态向上传递的过程是通过函数返回值来实现的。每次dfs调用返回一个包含两个元素的数组父节点接收这个数组后提取出需要的值进行计算然后返回自己的两个状态。整个过程不需要任何全局变量或额外的数据结构。但这里有一个语言层面的细节需要注意。在 Java 中每次返回数组都会在堆上分配内存如果树的节点数很大比如 10^5 级别频繁的数组分配可能会带来 GC 压力。这时候可以考虑用一个长度为 2 的int[]数组池来复用或者直接返回一个long类型的编码值把两个 int 打包成一个 long。不过对于大多数面试场景来说直接返回数组完全够用不需要过度优化。在 Python 中返回元组(selected, not_selected)比返回列表更轻量因为元组是不可变对象创建和销毁的开销更小。这是一个很小的优化点但在大规模数据下会有可感知的差异。5.3 不同语言实现的性能差异我分别在 Python、Java 和 C 中实现过这道题实测下来的性能差异还是比较明显的。C 的递归版本在 10^5 个节点的树上大约需要 1-2 毫秒Java 大约 3-5 毫秒Python 则需要 20-30 毫秒。这个差异主要来自函数调用开销和内存分配效率。如果你在面试中使用 Python而面试官对性能有要求可以考虑把递归改成迭代或者用functools.lru_cache来缓存结果虽然这道题不需要缓存但加上也不会有坏处。不过大多数情况下面试官更看重的是你的思路和代码正确性而不是微秒级的性能差异。有一个我在实际项目中总结的经验树形 DP 的递归深度如果可能超过 1000 层在 Python 中一定要手动设置sys.setrecursionlimit否则会抛出RecursionError。这个坑我在一次线上笔试中踩过当时树的深度达到了 5000 层默认的递归限制是 1000直接导致程序崩溃。6. 这道题教会我的树形DP通用套路6.1 识别树形DP问题的三个信号刷了足够多的题之后我发现树形 DP 问题通常有三个明显的信号。第一问题涉及树结构上的最优决策比如最大值、最小值、方案数。第二决策之间存在父子约束关系选了父节点就不能选子节点或者选了父节点就必须选子节点。第三问题的解可以通过子问题的解组合得到具有最优子结构性质。当你看到这三个信号同时出现时基本可以确定是树形 DP。接下来要做的就是定义状态每个节点需要向上层返回什么信息通常是一组与决策相关的值比如选和不选两种情况下的最优解。6.2 状态定义的通用模板树形 DP 的状态定义有一个通用模板对于每个节点定义一组状态表示在以该节点为根的子树中满足某种约束条件下的最优解。状态的数量取决于约束条件的复杂度。对于这道题约束只涉及父子相邻关系所以每个节点只需要两个状态。如果约束更复杂比如选了父节点后子节点和孙子节点都不能选那状态可能需要扩展到三个或更多。但核心思路是一样的把约束条件编码到状态中然后推导状态转移方程。6.3 从这道题延伸出去的变体这道题有几个常见的变体值得练习。第一个变体是树上的最大独立集本质上和这道题一模一样只是把金额换成了节点权重。第二个变体是打家劫舍 IV把树换成了图但图上有环需要用拓扑排序或者基环树 DP 来处理。第三个变体是监控二叉树每个节点可以放摄像头摄像头能覆盖父节点和子节点求最少需要多少个摄像头。这道题的难度更高状态定义也更复杂但核心思路仍然是树形 DP。我个人的建议是先把这道题吃透然后去做监控二叉树LC.968。那道题的状态定义需要三个值当前节点有摄像头、当前节点无摄像头但被覆盖、当前节点无摄像头且未被覆盖。如果你能独立推导出那道题的状态转移方程说明你对树形 DP 的理解已经到位了。7. 我在实际编码中踩过的五个坑7.1 空节点返回值不一致导致的错误第一个坑是我在早期写递归时对空节点的处理不一致。有时候返回null有时候返回[0, 0]导致父节点在计算时需要做额外的空判断。后来我统一了规范所有空节点一律返回[0, 0]这样父节点的计算逻辑可以保持一致不需要任何额外的边界判断。这个坑看起来很小但在实际编码中非常容易犯。尤其是在面试的紧张环境下你可能会不自觉地写出if (left ! null)这样的判断然后代码里到处都是空指针检查逻辑变得支离破碎。统一空节点的返回值可以让代码简洁很多。7.2 状态索引写反导致的隐蔽bug第二个坑是状态数组的索引写反。我习惯用[selected, not_selected]的顺序但有一次在计算not_selected时不小心写成了max(left[0], left[1])和max(right[0], right[1])看起来没问题但实际上left[0]是selectedleft[1]是not_selected取最大值是对的。问题出在计算selected时我写成了node.val left[0] right[0]这就错了因为选当前节点时子节点不能选应该用left[1]和right[1]。这个 bug 非常隐蔽因为代码不会报错只是结果不对。我调试了将近二十分钟才发现是索引写反了。从那以后我养成了一个习惯在代码中明确写出变量名而不是直接用索引。比如left_selected, left_not_selected dfs(node.left)这样即使写错了也能一眼看出来。7.3 递归深度超出限制的线上事故第三个坑是在一次线上笔试中树的深度达到了 5000 层Python 默认的递归限制是 1000直接导致RecursionError。当时我完全没有预料到测试用例会这么极端代码在本地跑得好好的提交上去就挂了。解决方案很简单在代码开头加上sys.setrecursionlimit(10000)。但更重要的是在写递归之前先估算一下树的最大可能深度。如果题目没有明确说明树的规模保守一点把递归限制设大一些。或者干脆用迭代版本彻底避免递归深度的问题。7.4 对相邻理解的偏差第四个坑是对题目中相邻的理解有偏差。题目说的是直接相连的父子节点不能同时被选但我一开始理解成了所有相邻节点包括兄弟节点。这导致我在状态定义时多考虑了一层约束把问题复杂化了。后来仔细读题才发现约束只涉及父子关系兄弟节点之间没有约束。这个理解偏差让我多花了十几分钟去推导一个错误的状态转移方程。所以我的经验是做题之前一定要把题目中的约束条件读清楚最好用自己的话复述一遍确认理解无误后再开始编码。7.5 忽略节点值为零或负数的情况第五个坑是忽略了节点值可能为零的情况。题目说的是非负整数意味着节点值可以是 0。如果节点值为 0选它和不选它对于金额的贡献是一样的但选它会影响子节点的选择。这时候max(selected, not_selected)可能会返回两个相等的值你需要确保代码在这种情况下仍然正确。更极端的情况是节点值为负数虽然这道题明确说了非负但有些变体可能会有负数。如果节点值为负选它反而会减少总金额那最优策略就是永远不选它。这时候状态转移方程需要调整selected的计算需要加上node.val如果node.val是负数selected自然会比not_selected小取最大值时会自动选择不选。所以代码本身不需要修改但你需要理解这个逻辑才能在面试中解释清楚。8. 面试中如何清晰表达这道题的解法8.1 从暴力递归到最优解的演进叙述在面试中我建议按照暴力递归 → 发现重复计算 → 引入状态定义 → 推导转移方程 → 分析复杂度的顺序来叙述。这样面试官能清楚地看到你的思考过程而不是直接抛出一个最优解。具体来说你可以先描述一个最朴素的递归思路对于每个节点尝试选和不选两种情况递归地计算子树的结果。然后指出这个思路的问题同一个节点的状态会被重复计算时间复杂度是指数级的。接着引入状态定义每个节点返回两个值分别表示选和不选时的最优解。最后推导转移方程并分析时间复杂度和空间复杂度。这个叙述过程大约需要 3-5 分钟但能让面试官充分了解你的思维深度。我在面试中用过这个套路面试官的反馈是思路很清晰能看出你是真正理解这道题的。8.2 状态定义的画图解释技巧如果面试是面对面的或者允许共享屏幕我强烈建议画一棵简单的树来解释状态定义。比如画三个节点根节点值为 3左子节点值为 2右子节点值为 3。然后手动计算选根节点和不选根节点两种情况下的结果让面试官直观地看到状态转移的过程。画图的好处是能把抽象的状态定义具象化面试官一眼就能看懂你的思路。而且画图的过程中你自己也能发现一些逻辑上的漏洞。我在面试中养成了一个习惯只要是树形或图形相关的问题先画图再写代码。这个习惯帮我避免了很多低级错误。8.3 复杂度分析的完整表述复杂度分析是面试中容易被扣分的环节。很多人只会说时间复杂度 O(n)空间复杂度 O(h)但面试官可能追问为什么是 O(n)O(h) 中的 h 是什么最坏情况下是多少完整的表述应该是时间复杂度 O(n)因为每个节点在递归过程中只被访问一次每次访问做常数时间的计算。空间复杂度 O(h)其中 h 是树的高度主要是递归调用栈的开销。对于平衡二叉树h O(log n)对于退化成链的树h O(n)。如果考虑迭代版本空间复杂度是 O(n)因为需要额外的哈希表来存储所有节点的状态。这样的表述既完整又准确能体现出你对复杂度分析的深入理解。9. 从这道题看动态规划的本质刷完这道题之后我对动态规划的理解又深了一层。动态规划的本质不是填表也不是找转移方程而是用状态来编码决策的约束用转移来组合子问题的解。这道题中状态就是选当前节点和不选当前节点约束就是父子不能同时选转移就是根据子节点的状态来计算当前节点的状态。这个思路可以推广到很多问题上。比如监控二叉树中状态是有摄像头无摄像头但被覆盖无摄像头且未被覆盖约束是摄像头能覆盖父节点和子节点转移是根据子节点的状态来决定当前节点是否需要摄像头。再比如树上的最大匹配中状态是当前节点是否已匹配约束是匹配的边不能共享端点转移是根据子节点是否已匹配来决定是否与当前节点匹配。所以我的建议是不要只记住这道题的代码而是要理解它背后的思维框架。当你遇到一个新的树形 DP 问题时先问自己三个问题每个节点需要返回什么信息这些信息如何组合空节点怎么处理回答了这三个问题状态转移方程自然就出来了。10. 一些值得反复练习的同类题目如果你想巩固树形 DP 的思维我推荐按以下顺序练习这几道题。第一道是 LC.337 本身先把这道题吃透。第二道是 LC.968 监控二叉树状态定义更复杂需要三个状态。第三道是 LC.124 二叉树中的最大路径和虽然严格来说不是树形 DP但涉及子树信息的向上传递思路很接近。第四道是 LC.543 二叉树的直径同样是利用子树信息来计算全局最优解。每道题做完之后不要急着看下一道而是回头想一想这道题的状态定义是什么转移方程是怎么推导出来的和上一道题有什么异同这样反复对比你就能逐渐建立起一套属于自己的树形 DP 解题模板。我在实际刷题过程中发现同一类型的题目做上五六道之后再遇到新的题目时大脑会自动开始分析状态定义和转移方程而不是像一开始那样毫无头绪。这种题感的建立需要时间和练习量但一旦建立起来解题效率会有质的飞跃。最后分享一个我在实际编码中的小技巧写完递归代码后先用一棵最简单的树比如只有一个节点或者三个节点的满二叉树手动模拟一遍确认返回值正确后再提交。这个习惯帮我抓出了很多边界条件的 bug尤其是在处理空节点和叶子节点时特别有效。