如果让我在LeetCode题库里挑一道最容易让人写出一份看起来对、提交却错的二叉树题我大概率会选第543题——二叉树的直径。这题在LeetCode热门100题里几乎是必刷的存在刷题指南里也常常把它排在二叉树递归入门的第一梯队很多人周赛前一晚会临时翻它的题解。题目本身一句话就能说完给定一棵二叉树返回这棵树的直径长度也就是任意两个节点之间路径中边的最大数目。我第一次做这题时心里想的是这还不简单最长路径要么经过根节点那就是左子树高度加右子树高度要么不经过根节点那就递归进左右子树里去找。于是第一版代码十分钟写完自测几个用例全部通过一提交WA。后来我才意识到这道题的坎不在于知不知道公式而在于对递归返回值的定义有没有想清楚。这篇文章把我踩过的坑、评论区里反复出现的问题、以及这题和一类树形DP题目的关系一次性讲透适合所有在刷树专题或者准备面试的读者。1. 直径的定义游戏为什么答案总比直觉少个11.1 长度单位是边数不是在数节点个数先看原题示例。输入一棵这样的二叉树1 / \ 2 3 / \ 4 5最长路径是4 - 2 - 1 - 3也可以走5 - 2 - 1 - 3答案给的是 3。这条路径明明经过了 4 个节点为什么答案是 3因为题目统计的是边数。4 个节点首尾相连中间只隔了 3 条边所以直径是 3。如果把直径理解成路径上一共经过多少个节点你会在所有写法里凭空多出 1而且这个偏差不固定——它只在路径确实存在的时候出现空树和单节点场景又会把你绕晕。这个定义上的细节是评论区大量为什么答案差一问题的源头。LeetCode 原题的官方定义写得很清楚直径是任意两个节点之间路径长度的最大值而路径长度用边数衡量。后续写代码时递归函数的返回值也必须保持这个口径否则全盘皆输。1.2 一个让根节点必经论翻车的反例第一版错解为什么错因为我默认了最长路径一定经过根节点。来看一棵我自己构造的树1 / \ 2 3 / \ 4 5 / \ 6 7 / \ 8 9直觉上你可能觉得从最深的叶子 8 走到最深的叶子 9路径会穿过根节点 1。算一下8-6-4-2-5-7-9这条路径确实很长但它走的是 2 的左子树和右子树并没有经过根节点 1。它的边数是 6。如果只算根节点左子树高度 根节点右子树高度得到的是 4和正确答案 6 差了一大截。这棵树就足以证明最长路径完全可能藏在某个子问题内部和根节点没有半点关系。这也是为什么左高 右高这种公式只在特定形态的树上成立不能当作通用解法。2. 我踩的第一版错解从只算根到三选一2.1 只算左高 右高一看就会一测就错先看我最初写的版本class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: if not root: return 0 return self.maxDepth(root.left) self.maxDepth(root.right) def maxDepth(self, node): if not node: return 0 return max(self.maxDepth(node.left), self.maxDepth(node.right)) 1在[1, 2, 3, 4, 5]这棵示例树上这段代码能算出正确结果。这很具有迷惑性。我拿几个普通用例一跑全对然后信心满满地提交结果在某个隐藏用例上挂了。问题在于它把所有希望都寄托在根节点会成为最高点。可最长路径的最高点也就是路径上最接近整棵树根的那个节点可以是任意节点。一旦最长路径出现在某个子树内部左高 右高就完全失效。更隐蔽的是这类错误通常只在特定形态的用例上暴露。如果你平时刷题只用平衡树、满二叉树做自测根本触发不了错误分支于是会带着错误理解浪费大量时间。2.2 三选一版本思路对了但性能崩了意识到最长路径不一定经过根节点之后我又写了一个三选一版本直径取三者最大——左子树的直径、右子树的直径、左子树高度加右子树高度。思路本身完全正确因为整棵树的直径无非就是这么三种情况。class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: if not root: return 0 left_d self.diameterOfBinaryTree(root.left) right_d self.diameterOfBinaryTree(root.right) left_h self.maxDepth(root.left) right_h self.maxDepth(root.right) return max(left_d, right_d, left_h right_h) def maxDepth(self, node): if not node: return 0 return max(self.maxDepth(node.left), self.maxDepth(node.right)) 1这个版本的自测结果非常稳定但在极端情况下性能会崩。原因很直接diameterOfBinaryTree本身要递归整棵树而每次递归又调用maxDepth把当前子树重新遍历一遍。对于退化成链表的斜树每一层都要重复扫描剩余的所有节点总工作量约等于N (N-1) (N-2) ...复杂度退化成 O(N²)。LeetCode 的用例规模一大这个版本就会超时。我后来复盘时意识到问题出在高度信息和直径统计被硬拆成了两条独立递归通道导致相同的子树被反复遍历。正确做法是把两件事合并到同一次递归里完成。3. 标准解法一次后序遍历完成统计和传值两份差事3.1 递归函数到底该返回什么标准解法只需要一个递归函数但要让这个函数同时承担两个职责返回值以当前节点为根的子树的最大向下深度也就是从当前节点出发往下走到任意叶子时最长能走的边数。全局统计在函数体内用当前节点左子树的深度加上右子树的深度更新一个外部变量这个外部变量最终就是直径。为什么这样设计想象每个子树是一个向领导汇报的员工。员工向上级汇报的只有一句话我这条线往下最长能延伸多少。而作为领导的当前节点在听完左边和右边两位下属的汇报后会做两件事第一看看左手长度 右手长度能不能破全公司纪录第二从自己左、右两侧里挑一个更长的方向加上自己这一层继续向上汇报。这样的好处是每个节点只被访问一次信息从下往上流动没有重复劳动。递归的后序性质天然保证了先算完子树再处理当前节点正好满足我们需要的统计顺序。3.2 为什么 left right 不用再加 1这是评论区出现频率最高的困惑点之一。许多人会疑惑left是左子树深度right是右子树深度路径经过当前节点时不应该还要加上当前节点自身吗为什么代码里写的是left right而不是left right 1关键在于口径。如果left表示从左子节点出发向下走到某个叶子最多经过的边数那么一条从左子树最远叶子出发、经过当前节点、再伸向右子树最远叶子的路径它的总边数就是left right。左边贡献left条边右边贡献right条边当前节点在中间只起到连接作用不额外增加边。单节点的情况可以验证左右子树深度都是 00 0 0直径为 0完全符合题目定义。如果你把left和right理解成从当前节点开始往下包含节点的个数那答案就要写成left right 1但最后还得处理减一的问题非常容易混乱。我的建议是统一采用边的口径代码里所有深度都用边数最后直接返回left right的最大值即可。3.3 完整代码与复杂度Python 版本class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: self.ans 0 def dfs(node): if not node: return 0 left dfs(node.left) right dfs(node.right) self.ans max(self.ans, left right) return max(left, right) 1 dfs(root) return self.ansJava 版本class Solution { int ans 0; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode root) { if (root null) return 0; int left dfs(root.left); int right dfs(root.right); ans Math.max(ans, left right); return Math.max(left, right) 1; } }时间复杂度 O(N)每个节点最多访问一次。空间复杂度 O(H)H 是树高递归栈的深度等于树高。最坏情况下树退化成链表H 接近 N空间复杂度会退化到 O(N)。这一点经常被面试官追问别下意识说成 O(logN)只有平衡树才是 O(logN)。3.4 正确性依赖一个事实每条路径都有一个拐点为什么枚举所有节点、更新left right就足够覆盖整棵树的最长路径关键在一个事实任何一条路径无论它在树里绕得多远都存在一个最高点——也就是路径上离整棵树根最近的节点即路径两端点的最近公共祖先。拿8 - 6 - 4 - 2 - 5 - 7 - 9这条路径举例它的最高点是 2。当递归遍历到节点 2 时left恰好是往 8 方向延伸的深度right恰好是往 9 方向延伸的深度于是self.ans就能被这条路径的长度刷新。我们不知道最长路径到底以哪个节点为最高点所以就让递归把所有节点都检查一遍答案一定在其中。4. 实测报告最常见翻车点与应对方式4.1 self.ans 不重置本地批量测试连环挂很多人把力扣的代码搬到本地做批量测试时会碰到一个很奇怪的场景单个用例单独跑答案全对一旦写个循环连续测试多棵树从第二棵树开始答案就偏大。问题出在self.ans这个实例变量上。如果每次都复用同一个Solution对象上一棵树留下的ans值会残留到下一棵树导致结果只增不减。虽然力扣判题时一般会重新构造实例但本地自测、单元测试、以及面试现场手写代码时这个坑非常真实。正确的习惯是在diameterOfBinaryTree入口处显式重置def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: self.ans 0 # 后续递归从这里开始哪怕你觉得我从来不会复用实例也建议加一行成本极低但可以避免一次诡异故障。4.2 边界树自查表写完代码后我建议用下面这张表快速自查避免低级失误输入形态预期直径说明None0空树没有任何路径只有一个节点0单节点之间路径长度为 0两个节点根 左子1只有一条边三个节点左链1-2-32从根走到最深处叶子示例[1,2,3,4,5]3最远路径穿根节点前文构造的非穿根树6最长路径发生在左子树内部特别提醒一下斜树也就是退化成链表的树。它的直径就是N - 1因为最远的两个端点必然是链的首尾。4.3 树大了递归爆栈迭代后序的写法Python 默认递归深度在 1000 左右如果树高超过这个限制标准递归写法会直接抛RecursionError。面试官有时会追问一句如果节点数量到 10^5 级别怎么办这时候迭代法就能派上用场。思路是手动模拟后序遍历的入栈出栈过程每个节点分两个状态第一次出栈表示还没处理子节点再次入栈第二次出栈时左右子树深度都已经算好可以更新答案并计算当前节点深度class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: ans 0 depth {None: 0} stack [(root, 0)] if root else [] while stack: node, state stack.pop() if state 0: stack.append((node, 1)) if node.left: stack.append((node.left, 0)) if node.right: stack.append((node.right, 0)) else: left depth[node.left] right depth[node.right] depth[node] max(left, right) 1 ans max(ans, left right) return ans这里用字典depth记录每个节点算好的深度None统一记 0。状态 0 表示首次访问状态 1 表示子节点处理完毕可以结算当前节点。逻辑和递归版本完全一致只是把系统调用栈换成了显式栈。4.4 口径混用left right 1 到底什么时候加评论区最常见的报错是我按题解写的答案总是多 1。这类问题几乎都是口径混用。如果你在dfs里返回的是包含当前节点的最大节点数那么left和right的语义就变成左右子树的最大节点数此时经过当前节点的路径节点数应该是left right 1转成边数还要再减 1。这里有个简单的自检方法单节点。如果dfs(单个节点)返回 1说明你用的是节点数口径如果返回 0说明用的是边数口径。选边数口径代码最干净。5. 从 543 到一类树形 DP 题状态与答案必须分开5.1 最长同值路径为什么不能直接抄 543 的返回逻辑LeetCode 687 题最长同值路径是绝佳的对比题它要求在路径上所有节点值都相同的前提下找最长路径。很多人会把 543 的代码原封不动抄过去结果全错。原因在于543 中任意子树深度都能无条件往上传递而 687 中只有当前节点和子节点值相等时子树的深度才能被父节点利用。具体写法是先递归算左右子树的深度如果左子节点存在且值和当前节点不同就把左深度置 0右子同理。答案更新依然用左侧深度加右侧深度但返回值只取左右中较大的那个未置零的那一侧。class Solution: def longestUnivaluePath(self, root: Optional[TreeNode]) - int: self.ans 0 def dfs(node): if not node: return 0 left dfs(node.left) right dfs(node.right) if node.left and node.left.val node.val: left 1 else: left 0 if node.right and node.right.val node.val: right 1 else: right 0 self.ans max(self.ans, left right) return max(left, right) dfs(root) return self.ans这个对比揭示了一个通用模式递归函数返回的是可以被父节点继续拼接的状态而全局答案记录的是以当前节点为转折点的局部最优。这两个角色必须由不同变量承担不能混为一谈。5.2 在无向图上求直径套路完全不同如果你在二叉树之外遇到求树的直径的题比如在一棵无向树或一般无向图上求最远两点距离二叉树里的递归后序思路当然也适用但还有另一个更简洁的贪心方法从任意点出发BFS/DFS 找到最远点 u再从 u 出发BFS/DFS 找到最远点 vu 到 v 的路径就是一条直径。这个方法只适用于边权都相等的图或树。如果边权是任意正数这个贪心就不成立了还是得回到树形 DP。543 正好是树形 DP 在二叉树上最朴素的形态理解了它之后再接触 LeetCode 124 题二叉树中的最大路径和会顺利很多——124 的答案更新要加当前节点值而且需要考虑负值截断。5.3 面试官可能加的三个追问面试中见过几种常见追问这里一并列出来如果输出最长路径本身而不只是长度怎么写通常需要额外记录每个节点的左右子深度方向并在更新答案时保存当前最长路径的左右端点最后从端点回溯拼接路径。如果必须用迭代法怎么写直接套上面 4.3 的显式栈版本注意入栈顺序不改变结算逻辑。能不能优化到 O(logN)不能因为最远路径可能藏在任意子树内部必须访问整棵树才能拿到足够信息任何输入模型下线性扫描信息都是下限。从这题之后我刷树的题目多了一个习惯写递归之前先问自己两个问题——这个函数向上返回的是什么全局最优解在哪里更新这两个问题的答案通常不是同一个变量。这个习惯让我后来看 687、124 这类题时快了很多。如果你也在刷 LeetCode 的二叉树专题建议把 543 当作树形 DP 的母题来对待不是背代码而是把状态返回和答案统计分离的思想刻进脑子里。