第一次刷 leetcode543 二叉树的直径 的时候我心里想这题不是送分题吗递归算左子树高度再递归算右子树高度加起来一交就完事。结果 WA 教做人问题不是代码写崩了而是我把“直径”等同于“经过根节点的最长路径”完全忽略了题目里那行小字——这条路径可能穿过根节点也可能不穿过。这道题真正想考的东西恰好就在这个“可能不穿过”里。这篇文章我会用自己的刷题过程作为线索把 二叉树的直径 从暴力解到最优解完整拆一遍。除了 leetcode543 本身的解法我还会讲清楚三个容易被问倒的问题递归函数为什么返回高度而不是直径、全局变量在多测试用例下要怎么处理、以及同样的框架怎么迁移到最大路径和、同值路径这类题。无论你是刚开始刷二叉树的新手还是准备面试想加深理解这篇应该都能给你一些文档之外的东西。1. 题目看着简单但第一大坑在“直径不过根节点”1.1 先用具体例子建立直觉题目给的定义是一棵二叉树的直径长度是任意两个结点路径长度中的最大值。注意这里的路径长度按边数算不是按节点数算。比如下面这棵树1 / \ 2 3 / \ 4 5 / \ 6 7从 6 到 7 的路径是 6 → 4 → 2 → 5 → 7经过的边数是 4这就是这棵树的直径。注意这条路径的最高点是 2而不是整棵树的根节点 1。如果你一上来就算左右子树高度之和也就是 1 的左子树高度 3 加上右子树高度 1得到 4看起来误打误撞也对了但换个树形就完全不是这么回事。再看这个例子1 / \ 2 3 / \ 4 5 / 6这棵树如果单纯算 root 左子树高度 右子树高度得到 3 1 4。但实际直径是多少从 6 到 5 是 6 → 4 → 2 → 5边数是 3从 6 到 3 是 6 → 4 → 2 → 1 → 3边数是 4。所以这棵树真实的直径是 4它确实穿过了根节点但不代表所有情况都会穿过。真正让人翻车的例子是这样的1 / 2 / \ 3 4 / \ 5 6根节点只有左子树右子树为空。如果只算 root 的左高 右高得到 3 0 3。但树的真实直径在哪里从 5 到 6路径是 5 → 3 → 2 → 4 → 6一共 4 条边它完全在根节点的左子树内部压根没经过根节点。如果一开始就把“直径 左子树高度 右子树高度”当成公式用这题必挂。1.2 为什么“左子树高度 右子树高度”会失效这里要引入一个很重要的视角想象一棵树里任意一条路径把所有节点按深度拍扁一定会有一个深度最小的节点也就是这条路径的“最高点”。这个最高点可能恰好是整棵树的根但更多时候是树中间某个普通节点。以最高点为界路径被分成了两段左边从最高点向下延伸到某个叶子方向右边从最高点向下延伸到另一个叶子方向。所以在每个节点上它作为“路径最高点”时能形成的局部最长路径就是它左子树的高度加上右子树的高度。但这个局部最长路径只是“以该节点为最高点”的候选答案。整棵树的直径是遍历所有节点之后把每个节点当最高点算出来的局部最大值。如果只站在全局 root 这一个节点上计算就会漏掉大量以其他节点为最高点的、更长的路径。想清楚这一点解法思路就呼之欲出了遍历所有节点在每个节点处计算左子树高度 右子树高度维护一个全局最大值。这个思路本身是诞生暴力解法和最优解法的共同起点。2. 先写一个直观但不够高效的暴力版本2.1 每个节点都当一次路径最高点基于前面“最高点”的思路第一版代码其实很直接写一个计算树高的函数然后在每个节点上都调一次这个函数用左子树高度 右子树高度更新答案。class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: if not root: return 0 def max_depth(node): if not node: return 0 return 1 max(max_depth(node.left), max_depth(node.right)) self.res 0 def dfs(node): if not node: return # 把当前节点当作路径最高点 self.res max(self.res, max_depth(node.left) max_depth(node.right)) dfs(node.left) dfs(node.right) dfs(root) return self.res这个版本逻辑上是完全正确的它枚举了每一个可能成为路径最高点的节点也就在理论上覆盖了所有真实路径。因为任意一条路径都有且仅有一个最高点只要在那个最高点处计算左高 右高就不会漏掉这条路径。2.2 暴力解的复杂度瓶颈在哪里但这段代码的效率很差主要问题出在重复计算上。每走到一个节点max_depth 都要往下重新扫一遍整个子树而 dfs 本身又会把整棵树所有节点都访问一遍。说白了每一层的深度计算都被下一层的深度计算重复覆盖。一棵退化成链状的树是重灾区根节点算深度要扫 N 个节点第二个节点要扫 N-1 个依次累加下来总复杂度是 O(N²)。就算是一棵比较平衡的树每个节点的子树规模平均也有 log N整体也接近 O(N log N)。所以暴力解能过一部分测试用例但遇到退化树大概率超时。这个版本的意义更多是帮助理解“最高点枚举”的模型真正能提交的版本还是要从这个模型里继续优化把重复计算去掉。3. 一次后序遍历同时拿到高度与直径3.1 核心转变递归函数只负责返回高度顺带更新直径暴力解低效的根本原因是 计算高度 和 枚举最高点 这两件事被拆成了两套独立的递归。其实它们可以合并成一次遍历。做法是在后序位置也就是左右子树都递归完毕、回到当前节点时我们已经拿到了左子树和右子树各自的高度。这时候顺手做两件事用left right更新全局直径值返回max(left, right) 1作为当前节点的高度供父节点继续使用。这个设计的精妙之处在于递归函数同时承担了两个职责但返回值和全局变量的职责是分开的返回值永远表示“从当前节点向下走到最远叶子方向的最大边数”全局变量则累积“以每个节点为最高点的局部最大路径长度”。这也是面试里非常容易被追问的一个设计点递归函数为什么不直接返回直径而返回高度因为父节点需要拼接的是“半条路径”也就是从当前节点出发继续往下延伸的能力。如果返回直径父节点根本没法判断这条直径有没有经过当前节点也就无法安全地把它拼到更高层的路径里。返回max(left, right) 1含义非常干净从我这个节点出发往最深的那一侧继续走最多还能走多远。说得再直白一点子树内部的直径是它自己内部的事情对父节点来说没有利用价值父节点需要的只是“你这边最深能伸出去多少”。这个区别是整个最优解的核心理解了这个后序遍历的写法就不会再忘。3.2 用高度合并更新直径假设当前节点是 cur左子树高度是 L右子树高度是 R。那么经过 cur 这条“竖向的路径”能有多长当然是 L R即从左子树最深的地方一路向上走到 cur再一路向下到右子树最深的地方。虽然这条路径在物理上是一条折线、会拐弯但它经过的边数恰好就是 L R。所以我们只需要在每次递归回溯时执行直径 max(直径, L R) 返回 max(L, R) 1每一步计算量都是常数时间整棵树只会被完整遍历一次时间复杂度 O(N)。3.3 多语言实现与细节差异用 Python 写的话需要注意全局变量的作用域问题。我最初直接在类成员变量上维护结果代码也能跑但后来发现如果写单元测试同一个 Solution 实例被多次调用时成员变量可能残留上次的值导致答案越变越大。稳妥的写法是用嵌套函数 nonlocal或者用一个长度为 1 的列表做可变容器。class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: res 0 def dfs(node: Optional[TreeNode]) - int: nonlocal res if not node: return 0 left dfs(node.left) right dfs(node.right) res max(res, left right) return max(left, right) 1 dfs(root) return resJava 也有类似的坑如果res是类成员变量多个测试用例复用一个 Solution 实例时初始值不会自动归零。所以我习惯把res放到一个int[]数组里或者干脆在方法入口处重新赋值。class Solution { public int diameterOfBinaryTree(TreeNode root) { int[] res new int[1]; depth(root, res); return res[0]; } private int depth(TreeNode node, int[] res) { if (node null) { return 0; } int left depth(node.left, res); int right depth(node.right, res); res[0] Math.max(res[0], left right); return Math.max(left, right) 1; } }C 的写法更自由一点可以直接传引用或者定义类成员变量注意声明周期问题class Solution { public: int diameterOfBinaryTree(TreeNode* root) { int diameter 0; dfs(root, diameter); return diameter; } private: int dfs(TreeNode* node, int diameter) { if (!node) { return 0; } int left dfs(node-left, diameter); int right dfs(node-right, diameter); diameter max(diameter, left right); return max(left, right) 1; } };三种语言的核心逻辑完全一致空节点返回 0叶子节点因为左右子节点都空、max(0, 0) 1 1所以高度为 1。这个“1”的含义是父节点到该叶子节点之间有一条边千万别理解成叶子节点自身占了 1 个长度等你后面做某些变体题时容易被绕晕。4. 边界条件、复杂度分析与常见误区复盘4.1 边界情况逐个过一遍把题做对只是第一步能稳稳地说清楚边界情况才算真正掌握。我通常会在白板或草稿纸上把这几种情况全测一遍第一空树。root为None理论上没有节点直径是 0。代码走dfs时直接返回 0res 保持 0正确。第二只有一个节点的树。左右都是空left 0right 0res 更新为 0正确。很多人会在这里纠结“一个节点的直径到底是 0 还是 1”回到边数定义单节点到它自己没有边答案就是 0。第三链状树。每个节点只有一个子节点整棵树只有一条路径直径应该是节点数减 1也就是边数 N-1。用代码跑一遍每一层都只有一侧返回非零另一侧是 0所以每个节点更新 res 时 left right 实际上就等价于“当前节点这一侧往下最长的边数”。越靠近根部的节点这个值越大最终根节点处得到 N-1正确。第四平衡二叉树。比如满二叉树的情况下直径通常是两个最远叶子之间的距离代码会自然地在公共祖先节点处取到最大值。4.2 时空复杂度与“为什么是 O(N)”时间复杂度是 O(N)。整棵树的每个节点只会被访问一次而且在访问节点时做的操作是常数时间取左高、取右高、比较更新、返回一个最大值。这个效率来自后序遍历天然的信息复用——每个子树的高度只计算一次父节点直接复用子节点算好的结果完全没有重复扫描。空间复杂度则取决于递归深度也就是树的高度。完全平衡的二叉树高度是 O(log N)递归调用栈占用也就是 O(log N)一旦树退化成链递归深度会达到 N空间开销也会变成 O(N)。所以严格说空间复杂度是 O(H)其中 H 是树高最坏情况 O(N)。关于递归栈爆掉的问题我实际刷题时遇到过几次。当树特别深比如上万层时Python 默认递归深度只有 1000 左右即使你在 LeetCode 上提交通过了放到本地超深数据上也会直接 RecursionError。这时有两个选择一是用sys.setrecursionlimit调高递归限制但治标不治本二是改成显式栈做后序遍历或者用 Morris 遍历思想把空间压到 O(1)。不过考试和面试中用递归版本来表达思路完全够用真到工程环境再考虑迭代版优化不迟。4.3 我实际写代码时踩过的两个坑第一个坑是递归顺序写错。我一开始为了“看起来更简洁”试图在递归调用前就更新 resdef dfs(node): if not node: return 0 left dfs(node.left) # 必须先递归 right dfs(node.right) # 必须先递归 # 更新逻辑必须放在这里 return max(left, right) 1原因很简单在递归返回之前左右子树的高度根本还没算出来这时候去更新 res 只能拿到空数据。后序遍历的核心就是“先问子节点要到答案再回来处理自己”。顺序写反整道题就废了。第二个坑是路径长度定义搞混。LeetCode 的直径按边数算但有些变体题按节点数算还有些题目给的是“每个节点有值路径长度是所有节点值之和”。如果机械套用left right在最大路径和那道题里会出错因为负数节点值可能导致路径不值得延伸需要在递归时做截断处理。这一点后面展开说。5. 同类问题迁移直径思路能延伸到哪些地方5.1 变体一如果要求的是“最大路径和”而不是“最长边数”力扣 124 题二叉树中的最大路径和和 543 的框架几乎一样唯一的区别是每个节点都带权值而且节点值可能为负数。路径长度不是数边而是把所有经过节点的值加起来。递归逻辑仍然是在后序位置处理但多了关键的一步对于左右子树传来的贡献值如果小于 0 就当作 0因为负数的贡献只会拖累整条路径。class Solution: def maxPathSum(self, root: Optional[TreeNode]) - int: res float(-inf) def dfs(node): nonlocal res if not node: return 0 left_gain max(dfs(node.left), 0) right_gain max(dfs(node.right), 0) res max(res, node.val left_gain right_gain) return node.val max(left_gain, right_gain) dfs(root) return res这个题和 543 的对应关系很清晰。543 里返回max(left, right) 1124 里返回node.val max(left_gain, right_gain)543 里更新left right124 里更新node.val left_gain right_gain。本质都是“在最高点拼接左右两边的最优贡献”。5.2 变体二如果是 N 叉树LeetCode 上还有一道 N 叉树直径题力扣 1522把二叉树换成了多叉树。思路不变但“左右子树高度”要变成“所有子树高度里最大的两个”。具体做法是递归访问所有子节点拿到每个子节点返回的高度找出第一大和第二大的值用这两个值相加更新直径当前节点返回最大子高度 1。难点只在“找 top 2”这一步的编码可以用两个变量维护也可以排序后取前两个。5.3 变体三如果要求返回具体直径路径有些面试官会加问一句“能不能把这条最长路径本身也找出来”这时候后序遍历框架需要额外记录路径信息。在每个节点处更新直径时不仅记录left right的大小还要记录左子树最深来自哪个子节点、右子树最深来自哪个子节点。最后拿到全局最大直径后从对应节点出发回溯拼接整条路径。实现会比长度版复杂不少但核心还是“最高点枚举”这套模型。另外对于普通的无向树还有另一种经典解法先任选一个点 DFS 找到最远端点 A再从 A DFS 找到最远端点 BA 到 B 的路径就是直径。这个结论在一般树中成立也可以用来求二叉树的直径特别适合带权图或者需要路径本身的场景。两种方法各有利弊后序遍历适合面试时展示对树形结构的理解两次 DFS 的实现思路更直观还能顺便求路径。5.4 同值路径题唯一路径的“拼接条件”变了力扣 687最长同值路径要求找的是“路径上所有节点值都相同”的最长路径。框架还是后序遍历但拼接条件从“任意左右子树都能拼接”变成了“只有和当前节点值相等的子树才能拼接”。所以在递归时左右子节点传给当前节点的高度值只有在child.val node.val时才有效否则直接当成 0。这个改动其实是在提醒一件事直径类题目的底层框架是通用的不同的变体只是修改了“什么贡献值可以被继续向上传递”的条件。理解了这一点以后遇到各种新变体都不会慌。6. 面试与实战中的考查方式6.1 面试官到底想通过这道题看什么二叉树的直径 作为一道经典中等题出现频率很高但面试官想考察的重点通常不只是“能不能写出来”而是背后的几个层次第一层是基础能力会不会后序遍历能不能正确处理空节点和单节点的边界。这一层没过基本就结束了。第二层是抽象能力能不能解释清楚“为什么在节点处用左高 右高能覆盖所有路径”也就是前面反复强调的“最高点”模型。很多人能背出答案但讲不出原理面试官一追问就露馅。第三层是迁移能力面试官可能会追一个问题比如“如果这棵树有几万个节点递归会不会爆栈”或者“换成 N 叉树怎么做”或者“如果要求输出路径呢”。这些追问通常都比原题更能拉开差距。我个人建议刷这道题的时候不要只满足于 AC而是把以下几句话练到能自然说出来这条路径有一个最高点每个节点只需要把左右两侧最深的高度拼起来递归函数返回高度而不是直径是为了让父节点能够安全拼接全局变量在多次测试实例下要注意重置或使用局部容器。能把这些讲清楚比多刷十道题都有用。6.2 树的直径在工程里能干什么很多人觉得这种题就是面试用的实际工程中用不到。其实“树的直径”是一个很通用的度量在很多系统里都能碰到。举几个我实际遇到或见过的场景在分布式系统或网络拓扑中如果节点之间按树形结构组织最远的两个节点之间的通信时延基本决定了某些同步协议收敛时间的上界。这时候树的直径就是一个直接的性能指标。算出直径就知道一条广播消息最坏要经过多少跳才能传到最后到达的节点。在组织架构或者依赖关系树里评估一个变更从根节点逐层传播到所有叶子节点要经过多少层本质上也是求树高或直径的一部分。虽然工程里通常不会为了这个专门写一个 leetcode543 的解法但理解了思想调起代码来就很快。在编译器或表达式解析场景里AST抽象语法树中两个相距最远的操作数之间的距离可以用来评估表达式结构的复杂度。这种情况偶尔会用到类似后序遍历求直径的思路因为你不希望额外建图再跑多源最短路一棵树内部的信息用一次遍历就能全拿到。当然工程中大多数树结构并不会像竞赛数据那样退化成几万层的链直接用递归通常问题不大。但如果真的遇到超深层树记得至少能说出“递归会爆栈可以改成显式栈或 Morris 遍历”这个优化方向而不是愣在原地。7. 写在最后的小技巧从这道题沉淀下来的通用套路最后分享一个我刷了上百道二叉树题之后总结的习惯拿到一棵树的题目先别急着写代码先问自己三个问题——我从子节点那里需要什么信息我在当前节点局部能算出什么答案我需要向父节点上报什么信息对于 二叉树的直径 来说答案分别是需要左右子树的高度能算出以当前节点为最高点的局部路径长度向父节点上报当前节点向下的最大延伸高度。这三个问题一旦理清代码是水到渠成的事。后面做最大路径和、最长同值路径、N 叉树直径你会发现自己其实一直在回答同样三个问题只是具体数值和拼接条件在变。这道题最值钱的地方恰恰不是那个正确的提交而是你第一次 WA 之后终于意识到“路径可能不经过根节点”的那一刻。把那一刻的顿悟记下来以后遇到任何树形结构里的“最长路径”类问题你都能比大多数人更快地找到那个把所有路径统一起来的“最高点”。