第一次见到 LeetCode 124 题时我还在按部就班地刷二叉树的遍历、深度、翻转这类基础题。点开二叉树中的最大路径和第一反应是最大路径和不就是从根到某个叶子、把沿途节点值加起来取最大吗等我看清楚题目里路径可以从任意节点出发、到任意节点结束这句话才发现这道题根本不是简单递归能糊弄过去的。它排在 LeetCode 热门 100 题里也是少数能让你真正理解二叉树 递归 全局答案三者怎么配合的 Hard 题。这篇笔记记录了我从最初被卡住到把思路拆开、手推代码、补齐各种边界用例的完整过程适合那些递归返回值设计还不太笃定、想真正吃透树形 DP 思路的人读。1. 题目到底在问什么路径定义与两个容易忽略的边界1.1 路径不是你想的那条路LeetCode 124 题的路径定义是一棵二叉树中任意两个节点之间的一条简单路径路径上节点数至少为 1每个节点只能经过一次。这意味着起点不是根终点也不是叶子。路径可以是叶子到叶子也可以是某个节点到它的孙子节点甚至可以是单个节点。节点值可能是负数。路径和是所有经过节点的值之和最大值完全可能是负数当整棵树所有节点都是负值时。路径不能回头。在二叉树里一条路径如果从某个节点进入子树就只能一直往下走不能在某个地方折返回上层。这三个点加起来就排除了很多想当然的解法。比如你习惯性地写一个函数求从根出发到叶子最大路径和那只能覆盖以根为起点的直线型路径再比如你下意识觉得答案是正数初始化答案用 0遇到全负数用例就会全军覆没。1.2 一条路径在二叉树里只有两种形状把一个二叉树想象成一张倒挂的树形地图。任意两节点之间的路径如果把它投影到树上形态只会是这两种之一直线型从某个节点出发一路只朝一个方向往下走。比如示例里从 15 到 20 再到 -10这是一条方向一致的链。拐弯型以某个节点为山顶左右各收一条分支。比如 15 - 20 - 7这条路径经过 20 这个节点时拐了个弯把左子树和右子树各一条分支接了起来。为什么路径最多只能拐一次弯不能像蛇一样弯好几次因为路径要求简单、不重复经过节点。一旦你从某个节点向下走进一棵子树又回到这个节点再走进另一棵子树那这个节点就被经过了两次违反了路径定义。所以任意一条路径都存在一个唯一的最高点离根最近的那个节点路径在这个最高点处收进 0 条、1 条或 2 条向下的分支。这个观察是整个题解的核心。LeetCode 官方示例是这样的-10 / \ 9 20 / \ 15 7最大路径和是 42对应 15 - 20 - 7 这条拐弯路径而不是 -10 - 20 - 15 这种 25。之所以 42 最大是因为它绕开了根节点的 -10在 20 这个节点处把左右两边的正值 15 和 7 都收进来了。提示先想清楚路径最多拐一次弯这个几何事实后面理解递归返回值会轻松很多。很多人的代码错了不是因为不会写递归而是因为对路径形状的理解是模糊的。2. 从暴力枚举到树形 DP贡献值这个概念怎么来的2.1 为什么不能枚举端点最常见的暴力思路是枚举所有两个节点作为路径起点和终点然后求它们之间的路径和取最大值。这个思路本身没错但复杂度撑不住。一棵 n 个节点的二叉树节点对数量是 O(n^2)每对节点求一次路径上的节点和又需要 O(height)最坏情况下整体复杂度到 O(n^3)。在 LeetCode 这种节点数可能到几万的输入下必挂无疑。我们真正需要的是一次后序遍历把信息汇总的做法。也就是树形 DP把子问题的答案算出来在父节点合并最终得到全局答案。2.2 关键观察每棵子树只需要向上提供一个半条路回到 1.2 的结论。任意一条完整路径有一个最高点在最高点它能收进左右两条分支。但如果我们换一个视角从父节点的角度看子节点情况就不一样了。假设你在处理一个节点 node你已经递归算完了它的左子树和右子树。现在你想知道node 的父节点能以 node 为起点向下延伸出一条怎样的路径对于父节点来说它只需要 node 向下提供一条直线型路径不希望在 node 这里拐弯。一旦在 node 拐弯这条路径就没法继续向上接了。所以递归函数返回值的语义必须非常明确从当前节点出发向下延伸只能朝一个方向走能得到的最大路径和。这个值在题解里通常叫贡献值gain。计算方式也很直接左子树的贡献值记为 left_gain右子树的贡献值记为 right_gain。但 left_gain 和 right_gain 不能直接用要先和 0 比较取最大值。为什么因为如果左子树整体贡献是 -5父节点选择走左分支只会让路径和更小那父节点完全可以选择不走等价于贡献 0。于是当前节点的贡献值就是node.val max(left_gain, 0) max(right_gain, 0) // 这是完整路径用于更新答案 node.val max(max(left_gain, 0), max(right_gain, 0)) // 这是向上提供的单边贡献等等上面这两条要分清。第一条是以 node 为山顶的完整路径——它可以同时收进左右两条非负分支这是给全局答案用的第二条才是node 向上提供的半条路——它只能选左或选右其中一边这是返回给父节点用的。2.3 用个不恰当的但好懂的例子你可以把它想象成快递员从山顶往山下送快递。每个岔路口快递员可以决定走左边还是走右边甚至直接放弃某条支路。如果一条支路走到底累计收益是负的比如 -100那不如不走收益记 0。但是如果快递员只是想统计某个中转站最佳业绩那他可以把左右两条支路的收益都算进来——这个中转站就是路径的最高点。递归的返回值是快递员从这个节点往下走能拿到的最大单边收益它是一条还没结束的路全局答案则是这个节点作为中转站把两边支路都收下时的最大收益它是一条完整封顶的路。这两个量经常有人在代码里搞混后面第四章我会专门讲混用导致的错误。2.4 复杂度分析每个节点只被访问一次每个节点内部做常数次比较和加法所以时间复杂度是 O(n)。递归过程中会用到调用栈最坏情况下二叉树退化成一条链表时栈深为 O(n)平均情况下树高为 O(log n)空间复杂度记为 O(height)。3. 代码实现与两个关键设计返回值语义和答案初始值3.1 参考代码Python Java看完思路直接上代码。Python 版class Solution: def maxPathSum(self, root: Optional[TreeNode]) - int: self.ans float(-inf) def dfs(node: Optional[TreeNode]) - int: if not node: return 0 # 子树贡献和0取max负数分支直接放弃 left max(dfs(node.left), 0) right max(dfs(node.right), 0) # 以当前节点为“山顶”的完整路径 cur node.val left right self.ans max(self.ans, cur) # 向上返回单边贡献 return node.val max(left, right) dfs(root) return self.ansJava 版class Solution { private int ans Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node) { if (node null) return 0; int left Math.max(dfs(node.left), 0); int right Math.max(dfs(node.right), 0); ans Math.max(ans, node.val left right); return node.val Math.max(left, right); } }Python 让你少写一点样板代码但两个版本的逻辑完全一致。核心就三个动作后序遍历、更新全局答案、返回单边贡献。3.2 为什么答案初始值必须是负无穷很多人第一次写这个题会习惯性写int ans 0结果一提交全负数用例直接错。原因很简单当所有节点都是负值时最大路径和必然是负数可初始化成 0 意味着答案至少是 0于是最终返回 0而不是真实的负值。举个例子-1 / \ -2 -3树里所有路径的最大和是 -1单独取根节点正确答案是 -1。如果 ans 初始化为 0dfs 流程走完 ans 始终是 0提交直接 WA。所以必须初始化为Integer.MIN_VALUEJava或float(-inf)Python。3.3 空节点返回 0 的语义递归到空节点时返回 0表示空子树提供的贡献是 0父节点可以选择不选这条路。这个 0 和上面 left/right 与 0 取 max 的逻辑是一脉相承的对一个节点来说左右分支贡献至少可以是 0——大不了不选嘛。注意空节点返回 0 不参与全局答案更新全局答案只会在实际存在的节点上更新。题目保证至少有一个节点所以 ans 一定会被更新不会出现负无穷泄漏到最终结果的情况。3.4 手动推一遍官方示例的完整递归过程用最笨的办法把节点都推一遍你会彻底明白这段代码在做什么。还是这棵树-10 / \ 9 20 / \ 15 7递归到叶子节点 9left0right0cur9009ansmax(-inf,9)9返回 9。递归到叶子节点 15left0right0cur15ansmax(9,15)15返回 15。递归到叶子节点 7left0right0cur7ans157 没有超过 15返回 7。递归到节点 20leftmax(dfs(15),0)15rightmax(dfs(7),0)7cur2015742ansmax(15,42)42返回 20max(15,7)35。递归到根节点 -10leftmax(dfs(9),0)9rightmax(dfs(20),0)35cur-1093534ansmax(42,34)42返回 -10max(9,35)25。最终返回 42。注意一个细节根节点的 cur 是 34没有超过 42但它还是被计算并比较了一次。这说明全局答案的候选者不止一个每个节点都有机会成为最优路径的山顶算法只是把每个候选都算了一遍再取最大值。4. 实际写代码最容易踩的坑返回值混用、初始化错误和运行时错误4.1 把完整路径当贡献值返回是最隐蔽的错误我见过不少人第一次 AC 后回看代码总觉得return node.val max(left, right)里max(left, right)有点不对劲为什么不是left right如果你把left right返回给父节点会发生什么假设我们现在处理节点 20把20 15 7 42返回给 -10。那么 -10 把 42 当成左/右分支的贡献值再加上自己的 -10得到一条路径15 - 20 - 7 - -10 - 9。这条路径在 20 和 -10 两个节点处都拐了弯违反了每个节点只能访问一次的路径定义结果必然是错的。正确理解是这样的返回值是半条路它只能从当前节点往一个方向延伸全局答案是整条路它才允许在当前节点收下两个方向。这两个量语义不同必须分开处理。我自己后来再遇到类似题目都会先在注释里把返回值的语义写清楚再动手写代码。4.2 子树贡献不取 0路径和会被负数分支拖垮还有一类错误是忘记做max(dfs(left), 0)这步截断。比如一棵树根节点值是 5左子树是一条全负值的链最大单边和是 -100。如果不截断根节点更新答案时会算出 5 (-100) right把一个大负数带进来正确结果被严重低估。截断的本质是路径可以在任意节点停止不必走完一整棵子树。既然路径可以从 15 直接到 20 结束那它当然也可以从 5 直接结束、完全不进左子树。max(..., 0)就是在表达这条分支我可以选择不走。提示只要树里存在负值节点截断这一步就必不可少。面试中这道题的高频考点之一就是看你能不能说出为什么分支贡献要和 0 取 max。4.3 答案初始化的边界用例自查第一次刷完题建议你用这几个用例跑一遍自己的代码能检查掉 90% 的边界 bug用例预期结果说明单节点值为 33路径就是节点本身单节点值为 -3-3千万别返回 0答案负无穷初始化才能过全负数树如 -1 / -2 -3-1取最大的单个节点根节点 0左右子都是大负数0单独取根节点即可左右子树各有大正值根为负数左最大值 右最大值拐弯路径可以绕开负根不对这里要小心如果根为负跨根的路径会加上负数通常不如只取一侧上面表格里最后一行要额外解释跨根路径会把根节点值加进去而根节点值是负的所以通常跨根不如只取一侧。但在某些场景下左右两侧都很大加上一个负根还是比单侧大这时跨根仍是正确答案。反正代码里cur node.val left right会把所有情况都覆盖。4.4 为什么刷二叉树题总报运行时错误这个问题在搜索热词里出现频率很高结合这道题我要说三个最常见的运行时错误来源第一不用 chema 判空直接访问node.val。二叉树递归的常规写法必须先处理if not node或 Java 的if (node null)否则空节点访问属性会抛空指针异常。第二递归深度过深。LeetCode 的输入偶尔会把二叉树构造得非常偏斜甚至退化成单链表深度可能达到数万层。Python 默认递归深度限制在 1000 左右一旦超过会抛 RecursionError。处理办法是改用迭代后序遍历或者在刷题环境允许时调高sys.setrecursionlimit。Java 虽然没有默认递归深度限制但栈溢出问题在最坏情况下同样可能出现。第三可变变量在递归里的作用域问题。比如有人把 ans 定义成普通局部变量传入递归在子调用里改了ans但因为是按值传递父调用里看到的 ans 还是旧值。所以我才在代码里用self.ans或者 Java 的实例变量确保每次更新都作用在同一个变量上。Python 闭包里如果不用nonlocal声明内层函数写外层变量会直接报UnboundLocalError这也是这类题常见的运行时错误。5. 举一反三直径、最长同值路径与 124 题共用同一副骨架5.1 二叉树的直径543LeetCode 543 题的直径求的是任意两节点路径上的边数最大值和 124 题的节点值最大路径和几乎是同一道题。区别只有两点递归返回值从最大单边贡献和变成最大单边高度/深度。全局答案的合并公式从node.val left right变成left_depth right_depth。代码骨架几乎不用改def diameterOfBinaryTree(self, root): self.diameter 0 def depth(node): if not node: return 0 left depth(node.left) right depth(node.right) self.diameter max(self.diameter, left right) return max(left, right) 1 depth(root) return self.diameter先刷 543 再刷 124你会很自然地发现后序收集左右信息、合并更新答案、向上返回单边信息是同一套模板。5.2 最长同值路径687687 题要求找一条路径路径上所有节点值相同返回路径长度。思路仍然是后序但比 543 多了一个条件只有当子节点值和当前节点值相同时这条分支的贡献才保留否则贡献清零。def longestUnivaluePath(self, root): self.ans 0 def dfs(node): if not node: return 0 left dfs(node.left) right dfs(node.right) left_keep left 1 if node.left and node.left.val node.val else 0 right_keep right 1 if node.right and node.right.val node.val else 0 self.ans max(self.ans, left_keep right_keep) return max(left_keep, right_keep) dfs(root) return self.ans对比一下 124 题你会发现结构完全一样变的就是什么算贡献、怎么合并这两个位置。5.3 面试 follow-up如果要求输出具体路径怎么办有些面试官会追问你不仅要返回最大路径和还要把这条路径打印出来。这时候需要额外记录路径端点。思路是在原来的dfs里除了返回最大单边贡献值同时返回这条贡献路径对应的端点节点。更新全局答案时如果node.val left right超过了当前最大值就把左分支的最佳端点、右分支的最佳端点都记录下来。最后从两个端点沿着记录的 parent 关系拼出整条路径。这一步的复杂度仍然是 O(n)但代码量会多不少。建议平时练习时把这道扩展题也写一遍面试碰到就不会慌。5.4 从这道题延伸到更大的树形 DP 视野124 题看起来只是一道二叉树题但它背后是更通用的树形 DP 思想树上的问题如果发现某个节点的答案可以由左右子树的答案合并而来基本都可以用后序遍历 全局变量这个模式解决。除了前面说的直径、同值路径再比如打家劫舍 III二叉树版、二叉树最大独立集都是同一类思想先递归算子问题再在父节点决定如何合并。区别只在于合并规则。124 题合并规则是正分支都收进来打家劫舍 III 的合并规则是当前节点抢不抢决定了子节点能不能抢。骨架一致权衡不同。我自己实际刷题的体会是这类题不要急着看题解。拿到题目后先画一棵 4 到 5 层的小树自己在草稿上写出每个节点的 left、right、cur、返回值跑一遍完整的递归过程。等你能不看题解写出 124 题的代码再花二十分钟把 543 和 687 也刷了整个树形 DP 的套路基本就焊死在脑子里了。最后再分享一个小技巧递归函数写完后故意把答案初始化改成 0 跑一遍全负数用例亲眼看看错误结果长什么样。这样踩过一次坑之后面试写代码时会下意识地想起答案初始化成负无穷这个细节比背任何口诀都管用。 
长河君 · 2026/10/8 21:28:47 · 阅读 1.2k 二叉树最大路径和：从递归到树形DP的完整解题笔记
第一次见到 LeetCode 124 题时我还在按部就班地刷二叉树的遍历、深度、翻转这类基础题。点开二叉树中的最大路径和第一反应是最大路径和不就是从根到某个叶子、把沿途节点值加起来取最大吗等我看清楚题目里路径可以从任意节点出发、到任意节点结束这句话才发现这道题根本不是简单递归能糊弄过去的。它排在 LeetCode 热门 100 题里也是少数能让你真正理解二叉树 递归 全局答案三者怎么配合的 Hard 题。这篇笔记记录了我从最初被卡住到把思路拆开、手推代码、补齐各种边界用例的完整过程适合那些递归返回值设计还不太笃定、想真正吃透树形 DP 思路的人读。1. 题目到底在问什么路径定义与两个容易忽略的边界1.1 路径不是你想的那条路LeetCode 124 题的路径定义是一棵二叉树中任意两个节点之间的一条简单路径路径上节点数至少为 1每个节点只能经过一次。这意味着起点不是根终点也不是叶子。路径可以是叶子到叶子也可以是某个节点到它的孙子节点甚至可以是单个节点。节点值可能是负数。路径和是所有经过节点的值之和最大值完全可能是负数当整棵树所有节点都是负值时。路径不能回头。在二叉树里一条路径如果从某个节点进入子树就只能一直往下走不能在某个地方折返回上层。这三个点加起来就排除了很多想当然的解法。比如你习惯性地写一个函数求从根出发到叶子最大路径和那只能覆盖以根为起点的直线型路径再比如你下意识觉得答案是正数初始化答案用 0遇到全负数用例就会全军覆没。1.2 一条路径在二叉树里只有两种形状把一个二叉树想象成一张倒挂的树形地图。任意两节点之间的路径如果把它投影到树上形态只会是这两种之一直线型从某个节点出发一路只朝一个方向往下走。比如示例里从 15 到 20 再到 -10这是一条方向一致的链。拐弯型以某个节点为山顶左右各收一条分支。比如 15 - 20 - 7这条路径经过 20 这个节点时拐了个弯把左子树和右子树各一条分支接了起来。为什么路径最多只能拐一次弯不能像蛇一样弯好几次因为路径要求简单、不重复经过节点。一旦你从某个节点向下走进一棵子树又回到这个节点再走进另一棵子树那这个节点就被经过了两次违反了路径定义。所以任意一条路径都存在一个唯一的最高点离根最近的那个节点路径在这个最高点处收进 0 条、1 条或 2 条向下的分支。这个观察是整个题解的核心。LeetCode 官方示例是这样的-10 / \ 9 20 / \ 15 7最大路径和是 42对应 15 - 20 - 7 这条拐弯路径而不是 -10 - 20 - 15 这种 25。之所以 42 最大是因为它绕开了根节点的 -10在 20 这个节点处把左右两边的正值 15 和 7 都收进来了。提示先想清楚路径最多拐一次弯这个几何事实后面理解递归返回值会轻松很多。很多人的代码错了不是因为不会写递归而是因为对路径形状的理解是模糊的。2. 从暴力枚举到树形 DP贡献值这个概念怎么来的2.1 为什么不能枚举端点最常见的暴力思路是枚举所有两个节点作为路径起点和终点然后求它们之间的路径和取最大值。这个思路本身没错但复杂度撑不住。一棵 n 个节点的二叉树节点对数量是 O(n^2)每对节点求一次路径上的节点和又需要 O(height)最坏情况下整体复杂度到 O(n^3)。在 LeetCode 这种节点数可能到几万的输入下必挂无疑。我们真正需要的是一次后序遍历把信息汇总的做法。也就是树形 DP把子问题的答案算出来在父节点合并最终得到全局答案。2.2 关键观察每棵子树只需要向上提供一个半条路回到 1.2 的结论。任意一条完整路径有一个最高点在最高点它能收进左右两条分支。但如果我们换一个视角从父节点的角度看子节点情况就不一样了。假设你在处理一个节点 node你已经递归算完了它的左子树和右子树。现在你想知道node 的父节点能以 node 为起点向下延伸出一条怎样的路径对于父节点来说它只需要 node 向下提供一条直线型路径不希望在 node 这里拐弯。一旦在 node 拐弯这条路径就没法继续向上接了。所以递归函数返回值的语义必须非常明确从当前节点出发向下延伸只能朝一个方向走能得到的最大路径和。这个值在题解里通常叫贡献值gain。计算方式也很直接左子树的贡献值记为 left_gain右子树的贡献值记为 right_gain。但 left_gain 和 right_gain 不能直接用要先和 0 比较取最大值。为什么因为如果左子树整体贡献是 -5父节点选择走左分支只会让路径和更小那父节点完全可以选择不走等价于贡献 0。于是当前节点的贡献值就是node.val max(left_gain, 0) max(right_gain, 0) // 这是完整路径用于更新答案 node.val max(max(left_gain, 0), max(right_gain, 0)) // 这是向上提供的单边贡献等等上面这两条要分清。第一条是以 node 为山顶的完整路径——它可以同时收进左右两条非负分支这是给全局答案用的第二条才是node 向上提供的半条路——它只能选左或选右其中一边这是返回给父节点用的。2.3 用个不恰当的但好懂的例子你可以把它想象成快递员从山顶往山下送快递。每个岔路口快递员可以决定走左边还是走右边甚至直接放弃某条支路。如果一条支路走到底累计收益是负的比如 -100那不如不走收益记 0。但是如果快递员只是想统计某个中转站最佳业绩那他可以把左右两条支路的收益都算进来——这个中转站就是路径的最高点。递归的返回值是快递员从这个节点往下走能拿到的最大单边收益它是一条还没结束的路全局答案则是这个节点作为中转站把两边支路都收下时的最大收益它是一条完整封顶的路。这两个量经常有人在代码里搞混后面第四章我会专门讲混用导致的错误。2.4 复杂度分析每个节点只被访问一次每个节点内部做常数次比较和加法所以时间复杂度是 O(n)。递归过程中会用到调用栈最坏情况下二叉树退化成一条链表时栈深为 O(n)平均情况下树高为 O(log n)空间复杂度记为 O(height)。3. 代码实现与两个关键设计返回值语义和答案初始值3.1 参考代码Python Java看完思路直接上代码。Python 版class Solution: def maxPathSum(self, root: Optional[TreeNode]) - int: self.ans float(-inf) def dfs(node: Optional[TreeNode]) - int: if not node: return 0 # 子树贡献和0取max负数分支直接放弃 left max(dfs(node.left), 0) right max(dfs(node.right), 0) # 以当前节点为“山顶”的完整路径 cur node.val left right self.ans max(self.ans, cur) # 向上返回单边贡献 return node.val max(left, right) dfs(root) return self.ansJava 版class Solution { private int ans Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node) { if (node null) return 0; int left Math.max(dfs(node.left), 0); int right Math.max(dfs(node.right), 0); ans Math.max(ans, node.val left right); return node.val Math.max(left, right); } }Python 让你少写一点样板代码但两个版本的逻辑完全一致。核心就三个动作后序遍历、更新全局答案、返回单边贡献。3.2 为什么答案初始值必须是负无穷很多人第一次写这个题会习惯性写int ans 0结果一提交全负数用例直接错。原因很简单当所有节点都是负值时最大路径和必然是负数可初始化成 0 意味着答案至少是 0于是最终返回 0而不是真实的负值。举个例子-1 / \ -2 -3树里所有路径的最大和是 -1单独取根节点正确答案是 -1。如果 ans 初始化为 0dfs 流程走完 ans 始终是 0提交直接 WA。所以必须初始化为Integer.MIN_VALUEJava或float(-inf)Python。3.3 空节点返回 0 的语义递归到空节点时返回 0表示空子树提供的贡献是 0父节点可以选择不选这条路。这个 0 和上面 left/right 与 0 取 max 的逻辑是一脉相承的对一个节点来说左右分支贡献至少可以是 0——大不了不选嘛。注意空节点返回 0 不参与全局答案更新全局答案只会在实际存在的节点上更新。题目保证至少有一个节点所以 ans 一定会被更新不会出现负无穷泄漏到最终结果的情况。3.4 手动推一遍官方示例的完整递归过程用最笨的办法把节点都推一遍你会彻底明白这段代码在做什么。还是这棵树-10 / \ 9 20 / \ 15 7递归到叶子节点 9left0right0cur9009ansmax(-inf,9)9返回 9。递归到叶子节点 15left0right0cur15ansmax(9,15)15返回 15。递归到叶子节点 7left0right0cur7ans157 没有超过 15返回 7。递归到节点 20leftmax(dfs(15),0)15rightmax(dfs(7),0)7cur2015742ansmax(15,42)42返回 20max(15,7)35。递归到根节点 -10leftmax(dfs(9),0)9rightmax(dfs(20),0)35cur-1093534ansmax(42,34)42返回 -10max(9,35)25。最终返回 42。注意一个细节根节点的 cur 是 34没有超过 42但它还是被计算并比较了一次。这说明全局答案的候选者不止一个每个节点都有机会成为最优路径的山顶算法只是把每个候选都算了一遍再取最大值。4. 实际写代码最容易踩的坑返回值混用、初始化错误和运行时错误4.1 把完整路径当贡献值返回是最隐蔽的错误我见过不少人第一次 AC 后回看代码总觉得return node.val max(left, right)里max(left, right)有点不对劲为什么不是left right如果你把left right返回给父节点会发生什么假设我们现在处理节点 20把20 15 7 42返回给 -10。那么 -10 把 42 当成左/右分支的贡献值再加上自己的 -10得到一条路径15 - 20 - 7 - -10 - 9。这条路径在 20 和 -10 两个节点处都拐了弯违反了每个节点只能访问一次的路径定义结果必然是错的。正确理解是这样的返回值是半条路它只能从当前节点往一个方向延伸全局答案是整条路它才允许在当前节点收下两个方向。这两个量语义不同必须分开处理。我自己后来再遇到类似题目都会先在注释里把返回值的语义写清楚再动手写代码。4.2 子树贡献不取 0路径和会被负数分支拖垮还有一类错误是忘记做max(dfs(left), 0)这步截断。比如一棵树根节点值是 5左子树是一条全负值的链最大单边和是 -100。如果不截断根节点更新答案时会算出 5 (-100) right把一个大负数带进来正确结果被严重低估。截断的本质是路径可以在任意节点停止不必走完一整棵子树。既然路径可以从 15 直接到 20 结束那它当然也可以从 5 直接结束、完全不进左子树。max(..., 0)就是在表达这条分支我可以选择不走。提示只要树里存在负值节点截断这一步就必不可少。面试中这道题的高频考点之一就是看你能不能说出为什么分支贡献要和 0 取 max。4.3 答案初始化的边界用例自查第一次刷完题建议你用这几个用例跑一遍自己的代码能检查掉 90% 的边界 bug用例预期结果说明单节点值为 33路径就是节点本身单节点值为 -3-3千万别返回 0答案负无穷初始化才能过全负数树如 -1 / -2 -3-1取最大的单个节点根节点 0左右子都是大负数0单独取根节点即可左右子树各有大正值根为负数左最大值 右最大值拐弯路径可以绕开负根不对这里要小心如果根为负跨根的路径会加上负数通常不如只取一侧上面表格里最后一行要额外解释跨根路径会把根节点值加进去而根节点值是负的所以通常跨根不如只取一侧。但在某些场景下左右两侧都很大加上一个负根还是比单侧大这时跨根仍是正确答案。反正代码里cur node.val left right会把所有情况都覆盖。4.4 为什么刷二叉树题总报运行时错误这个问题在搜索热词里出现频率很高结合这道题我要说三个最常见的运行时错误来源第一不用 chema 判空直接访问node.val。二叉树递归的常规写法必须先处理if not node或 Java 的if (node null)否则空节点访问属性会抛空指针异常。第二递归深度过深。LeetCode 的输入偶尔会把二叉树构造得非常偏斜甚至退化成单链表深度可能达到数万层。Python 默认递归深度限制在 1000 左右一旦超过会抛 RecursionError。处理办法是改用迭代后序遍历或者在刷题环境允许时调高sys.setrecursionlimit。Java 虽然没有默认递归深度限制但栈溢出问题在最坏情况下同样可能出现。第三可变变量在递归里的作用域问题。比如有人把 ans 定义成普通局部变量传入递归在子调用里改了ans但因为是按值传递父调用里看到的 ans 还是旧值。所以我才在代码里用self.ans或者 Java 的实例变量确保每次更新都作用在同一个变量上。Python 闭包里如果不用nonlocal声明内层函数写外层变量会直接报UnboundLocalError这也是这类题常见的运行时错误。5. 举一反三直径、最长同值路径与 124 题共用同一副骨架5.1 二叉树的直径543LeetCode 543 题的直径求的是任意两节点路径上的边数最大值和 124 题的节点值最大路径和几乎是同一道题。区别只有两点递归返回值从最大单边贡献和变成最大单边高度/深度。全局答案的合并公式从node.val left right变成left_depth right_depth。代码骨架几乎不用改def diameterOfBinaryTree(self, root): self.diameter 0 def depth(node): if not node: return 0 left depth(node.left) right depth(node.right) self.diameter max(self.diameter, left right) return max(left, right) 1 depth(root) return self.diameter先刷 543 再刷 124你会很自然地发现后序收集左右信息、合并更新答案、向上返回单边信息是同一套模板。5.2 最长同值路径687687 题要求找一条路径路径上所有节点值相同返回路径长度。思路仍然是后序但比 543 多了一个条件只有当子节点值和当前节点值相同时这条分支的贡献才保留否则贡献清零。def longestUnivaluePath(self, root): self.ans 0 def dfs(node): if not node: return 0 left dfs(node.left) right dfs(node.right) left_keep left 1 if node.left and node.left.val node.val else 0 right_keep right 1 if node.right and node.right.val node.val else 0 self.ans max(self.ans, left_keep right_keep) return max(left_keep, right_keep) dfs(root) return self.ans对比一下 124 题你会发现结构完全一样变的就是什么算贡献、怎么合并这两个位置。5.3 面试 follow-up如果要求输出具体路径怎么办有些面试官会追问你不仅要返回最大路径和还要把这条路径打印出来。这时候需要额外记录路径端点。思路是在原来的dfs里除了返回最大单边贡献值同时返回这条贡献路径对应的端点节点。更新全局答案时如果node.val left right超过了当前最大值就把左分支的最佳端点、右分支的最佳端点都记录下来。最后从两个端点沿着记录的 parent 关系拼出整条路径。这一步的复杂度仍然是 O(n)但代码量会多不少。建议平时练习时把这道扩展题也写一遍面试碰到就不会慌。5.4 从这道题延伸到更大的树形 DP 视野124 题看起来只是一道二叉树题但它背后是更通用的树形 DP 思想树上的问题如果发现某个节点的答案可以由左右子树的答案合并而来基本都可以用后序遍历 全局变量这个模式解决。除了前面说的直径、同值路径再比如打家劫舍 III二叉树版、二叉树最大独立集都是同一类思想先递归算子问题再在父节点决定如何合并。区别只在于合并规则。124 题合并规则是正分支都收进来打家劫舍 III 的合并规则是当前节点抢不抢决定了子节点能不能抢。骨架一致权衡不同。我自己实际刷题的体会是这类题不要急着看题解。拿到题目后先画一棵 4 到 5 层的小树自己在草稿上写出每个节点的 left、right、cur、返回值跑一遍完整的递归过程。等你能不看题解写出 124 题的代码再花二十分钟把 543 和 687 也刷了整个树形 DP 的套路基本就焊死在脑子里了。最后再分享一个小技巧递归函数写完后故意把答案初始化改成 0 跑一遍全负数用例亲眼看看错误结果长什么样。这样踩过一次坑之后面试写代码时会下意识地想起答案初始化成负无穷这个细节比背任何口诀都管用。