从“树的直径”开始说起刷题时看到“39.二叉树的直径”这个标题可能不少人第一反应是“这不就是求树的最长路径吗”。但实际上这个题目藏着一个很容易踩进去的坑——它问的是任意两个节点之间路径的最大边数这个路径不一定经过根节点。很多人一开始默认路径必须经过根结果代码跑出来的答案是错的而且错得莫名其妙。二叉树直径Binary Tree Diameter是算法面试里的经典问题几乎每一版高频题单里都有它。它考的不仅是递归的熟练度更是你对“树形动态规划”有没有形成肌肉记忆。题目本身可以用一句话讲清楚给定一棵二叉树返回这棵树的直径即任意两节点之间路径中的最长边数。适合正在准备软件工程师笔试的人、刚接触树形DP的新手以及想系统整理递归模板的读者。这篇文章会用比较容易理解的方式把这道题的思路、代码、边界条件、常见误区全部拆开讲透。代码以Python为主中间会穿插我对几个关键细节的思考过程最后再聊几个相关的变体和扩展。1. 先把“直径”的定义吃透1.1 “任意两节点之间的路径”到底是什么意思拿一棵很常见的二叉树举例1 / \ 2 3 / \ 4 5这棵树的直径是多少答案是3。因为4到5这条路径或者4到3这条路径边数都是3。4到5的路径是4→2→1→5仔细数一下4→2是1条边2→1是2条边1→5是3条边不对1到5只有一条边4到5是4→2→1→5不对5是1的右子树的根上面画的树里5是2的右孩子4是2的左孩子那么4到5的路径是4→2→5只有2条边而4到3是4→2→1→33条边。所以这棵树的直径实际上是3最长路径是4→2→1→3。如果把2的两棵子树看成“左子树4右子树5”那么4到5只有2条边但因为1的右子树3很深不3就一个节点。所以这棵树里最远的两个叶子是4和3距离是4→2边1→1边2→3边3确实为3。从这个例子能看出一个关键点最长的路径往往经过某个中间节点这个节点相当于路径的“最高点”路径从它这里分别往两棵子树深处延伸。而这个最高点不一定是整棵树的根。如果最深的两片叶子都在同一棵子树里那么最高点就是那个子树的某个内部节点而不是根。1.2 直径和“高度”“深度”是两码事树的深度一般指从根到某个节点的边数树的高度通常指从根到最远叶子节点的边数也有人按节点数计。直径则完全不一样它描述的是任意两个节点之间的全局最大距离是一个“横向”的指标。很多人会把直径想成“左子树高度 右子树高度”。这个想法在路径经过根的时候是对的但路径不经过根时就不成立了。例如一条向左倾斜的链式树根只有左孩子这时直径完全在左子树内部跟根没有关系。所以解题时不能只算根节点的左高加右高而是要在“所有节点”上尝试这个公式然后取最大。这里有一个简单但极其重要的转化经过某个节点的最长路径长度等于“该节点左子树的最大高度”加上“该节点右子树的最大高度”。把所有节点都考虑一遍其中的最大值就是整棵树的直径。这个转化是整道题的核心。2. 核心思路从全局思考到每个节点2.1 一个关键观察每一条路径都有一个“拐点”任意一条路径都可以找到路径上离根最近的那个节点我习惯把它叫做路径的“拐点”。路径从这个拐点向下分成两支或只走一支一支往左子树最深的方向走另一支往右子树最深的方向走。如果只走一支说明另一支的深度为0这种情况下路径其实就是某棵子树内部的一条深度路径。因此如果对每个节点都计算“左子树最高点到右子树最高点的路径长度”那么全局最长的那条路径必然会被某个节点的这个计算值覆盖。理解这一点之后解法就清晰了递归遍历所有节点在遍历过程中维护一个全局变量不断用“左高度 右高度”去刷新它。这个思路的本质是“树形DP”。每个节点需要向父节点汇报自己的高度同时作为最高点尝试更新全局答案。先想清楚子问题再想清楚如何把子问题的结果组装起来是解这类题的通用心法。2.2 为什么不能简单地自顶向下找有个常见的错误思路先找到整棵树最深的叶子再找到离它最远的一个节点或者“从根开始分别在左右子树里找最深节点”。这样做的风险在于如果直径完全落在单侧子树里这种思路就完全失效。就算直径经过根如果你只顾着找“整体最深”也可能错过真正的最远组合。更关键的是这种做法在二叉树里没有明确的分治规则你没法保证局部最深的组合就是全局最远。而“遍历每个节点作为拐点”是穷举所有可能的最高点天然不会漏复杂度也只是O(n)。把问题拆细看其实是两件事一是子树高度怎么维护二是全局答案怎么更新。子树高度的定义必须前后一致不然计算会出现差一错误。下文我统一按“边数”来定义高度即空节点高度为0叶子节点高度为0一个节点的子树高度是 max(左高度, 右高度) 1。2.3 递归函数设计返回高度更新答案代码可以写成这样class Solution: def diameterOfBinaryTree(self, root) - int: self.ans 0 def dfs(node): if node is None: 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.ans递归做了两件事第一件递归地拿到左右子树各自的高度第二件用这两个高度拼出“经过当前节点的最长路径”并更新答案。每次返回给父节点的是当前子树的最大高度这样可以保证父节点在算自己的路径时拿到的是子树里“最有潜力”的那条分支。3. 一步一步手写实现3.1 代码骨架的逐行拆解第一步要明确空节点的高度约定空节点返回0表示没有路径可用叶子节点的左右子树高度都是0所以叶子返回 max(0, 0) 1 1即叶子到叶子自身的距离为0因为以叶子为拐点时left right 0。很多递归题都采用“空节点返回0”的习惯这个约定会让代码少掉很多if分支。第二步执行递归时顺序是后序遍历先算左子树再算右子树最后处理当前节点。原因很简单当前节点需要用左右子树的结果来组装自己的答案只有后序才能拿到这两个结果。第三步注意更新的时机每次递归进入一个节点时都尝试更新答案而不是只在根节点更新一次。因为在递归返回的过程中每个节点都有机会刷新全局最大值。如果只在根节点算一次那么路径不经过根的树就会算错。最后返回高度时一定要“1”因为要把到当前节点本身的这条边贡献给父节点。3.2 最容易踩的一个坑边数和节点数混淆二叉树直径在不同平台上的定义会有细微差别。有的题定义为“节点数”例如一棵只有一个节点的树直径按节点数算是1按边数算是0。LeetCode的“二叉树的直径”明确按“边数”计算。如果题目要求按节点数返回代码里的答案更新逻辑要改成 left right 1因为这个值表示路径经过的节点总数左子树深度对应的节点数 右子树深度对应的节点数 当前节点本身。叶子节点按节点数计高度时通常定义为1按边数计高度时定义为0。两种约定不能混用否则答案会多1或少1。我见过有同学在代码里用下面的方式定义高度if node is None: return 0 left dfs(node.left) right dfs(node.right) self.ans max(self.ans, left right 1) return max(left, right) 1这个写法如果题目要求返回边数就会出错。比如一棵三个节点的完全二叉树按节点数直径是3按边数直径是2。所以要养成习惯先把题目要求读清楚再确定使用哪种“1”规则。3.3 迭代方案用显式栈模拟递归如果面试里被要求手写非递归版本或者递归深度太深导致栈溢出可以用栈模拟后序遍历。思路是给每个节点打一个状态标记第一次入栈表示“待访问”第二次入栈表示“子树已经处理完可以结算”。def diameterOfBinaryTree(root) - int: if root is None: return 0 stack [(root, 0)] # (node, visited) height {} ans 0 while stack: node, visited stack.pop() if node is None: continue if visited 0: stack.append((node, 1)) if node.right: stack.append((node.right, 0)) if node.left: stack.append((node.left, 0)) else: left height.get(node.left, 0) right height.get(node.right, 0) ans max(ans, left right) height[node] max(left, right) 1 return ans这个版本用字典记录每个节点的高度本质上和递归做的事一样。需要注意入栈的时候要先压当前节点标记为已访问再压右孩子最后压左孩子因为栈是后进先出左孩子先进栈才能被先处理。处理顺序依然是左子树、右子树、当前节点。4. 复杂度分析与边界情况4.1 时间复杂度和空间复杂度递归版本每个节点只会被访问一次时间复杂度为O(n)n是节点总数。空间复杂度方面递归调用栈的深度取决于树的高度。对于平衡二叉树递归深度是O(log n)对于退化成链状的二叉树递归深度是O(n)。所以当树特别深时Python默认的递归深度限制1000左右可能不够需要手动调大或改用迭代方案。迭代版本用了一个哈希表存储所有节点的高度空间复杂度同样为O(n)。两种方案在数据规模较大时都能接受但递归写法更简洁迭代写法更稳。4.2 空树、单节点、链状树空树的直径是0因为没有任何路径。这个case在代码里天然成立dfs返回0ans保持为0。单节点树节点左右子树高度都是0left right 0直径是0。符合边数定义下“自己到自己的距离为0”。链状树比如每个节点只有左孩子一共n个节点1 \ 2 \ 3 \ 4最远距离是最深节点4到根1边数为3也就是n-1。递归处理时每个节点更新的是 left right其中一侧高度为0另一侧高度持续累加最后ans被更新为n-1。这个结果是符合直觉的。完全二叉树或满二叉树的直径通常等于最底层两个不同子树叶子之间的距离。以高度为h的满二叉树为例直径通常是2(h-1)因为最远的两个叶子一定分别位于根节点的左右子树里各自到根的距离都是h-1。4.3 后序遍历顺序为什么重要在递归版代码里更新答案是发生在左右递归调用之后。如果放在调用之前拿到的 left 和 right 就都是0不仅高度算不准答案也永远刷新不了。后序遍历的天然优势是自底向上组合信息。实际上树的所有DP类问题几乎都依赖这种从叶子到根的信息汇聚过程。理解这一点比背代码本身更重要。拿到任何一道“树形DP”问题第一件事都是确认子问题是什么父节点需要从子节点获取什么信息然后再考虑用先序、中序还是后序。绝大多数情况下答案都是后序因为父节点依赖子节点的计算结果。5. 常见问题与排查思路现象可能原因排查方法答案比预期多1按节点数口径计算边数检查叶子节点高度定义改为边数口径答案比预期少1返回高度时忘记1模拟单节点和三节点树验证大树上递归栈溢出树退化成链递归深度过大调大递归限制或改用迭代栈链状树答案为0只在根节点计算左右高度确认是在每个节点都更新了ans迭代版答案不对栈的出栈顺序与后序不一致检查是否先处理左子树再处理右子树我实际排查过的一个真实案例某位同学写的递归代码在普通树上全对但一测链状树就返回0。后来发现他只在根节点计算 left right没有在递归过程中更新全局变量。这说明他没有真正理解“每个节点都可能成为拐点”这一核心思想只是背了一个模板。另一个高频问题是用全局变量和类属性。递归函数内部访问外部变量时如果只读不写没问题但如果要更新答案最好声明为 self.ans 或使用列表包裹避免Python闭包作用域带来的赋值问题。6. 变体与延伸一个模板打天下6.1 求最长路径的节点数有些题目把“直径”定义成最长路径经过的节点总数。这时只需要把答案更新逻辑从 left right 改成 left right 1同时把叶子节点的高度约定改成按节点数计即叶子节点高度为1。这个改动虽然小但很多人会在面试时因为口径问题被扣分值得提前想清楚。6.2 二叉树中的最大路径和LeetCode 124题“二叉树中的最大路径和”和本题是孪生兄弟。题目允许路径穿过任意节点节点上有权重可能为负数要求返回路径上的最大节点权值之和。解法框架几乎一样def maxPathSum(root) - int: self.ans float(-inf) def dfs(node): if node is None: return 0 left max(dfs(node.left), 0) # 负数分支直接舍弃 right max(dfs(node.right), 0) self.ans max(self.ans, left node.val right) return node.val max(left, right) dfs(root) return self.ans对比两道题就能发现树形DP的核心模式是统一的子树返回“贡献值”当前节点尝试拼接“全局候选值”。差别只在于贡献值的定义方式——直径题贡献的是深度最大路径和题贡献的是路径权值和。6.3 多叉树直径如果把二叉树推广到多叉树思路依然成立只是每个节点的“候选路径”要取子树中深度最大的两个分支之和。实现时遍历每个子节点的高度记录最大值和次大值然后相加更新答案。这是一个很自然的扩展核心思想完全相同。多条DFS路径、带权边、带负权节点、需要输出具体路径而不是长度这些变体都是在基础模板上做增量修改。基础模板理解了变体就不会慌。7. 刷题之外的一些体感建议这个题刷完建议顺手把这几道题放在一起对比练习二叉树的最大深度、二叉树的最小深度、二叉树的直径、二叉树中的最大路径和、打家劫舍 III。它们的共同点是“每个节点向父节点返回一种贡献值同时用子问题的结果更新全局答案”。把这一类题放在一起刷可以快速形成树形DP的思维模式。我自己的经验是写递归函数时一定要在脑子里先把递归出口想明白也就是“node为空时返回多少”再把本层要做的三件事列出来拿左子树结果、拿右子树结果、组装并更新。脑子里有这三步写代码基本不会乱。最后再提一个小技巧在正式提交前用三个case自测——空树单节点树左右子树高度不等的树。尤其是第三种非常容易暴露“1”的时机问题。把这三个case跑通这个题就基本稳了。
