刷算法题的人应该都见过这么一道题二叉树的直径标题前面往往还挂着一个序号39。乍一看题目很短一句话就能说清——求一棵二叉树中任意两个节点之间最长路径的长度。但就是这道看似人畜无害的题我在不同场合见过不少人翻车有人把它当成“左子树高度加右子树高度”有人递归返回值写得稀里糊涂还有人压根没意识到这条最长路径可能根本不经过根节点。今天就把这道题从题目理解、思路推导、代码实现到避坑细节完整拆一遍。这道题适合谁看如果你是刚接触二叉树递归的新手这篇文章能帮你彻底搞懂“自底向上”的思考方式如果你已经刷过一遍但总觉得自己是靠背模板写出来的这篇文章能帮你把模板背后的逻辑打通。哪怕你只是准备面试想快速过一下经典题本文的易错点总结也能帮你省下不少时间。1. 先别急着写代码题目到底在问什么1.1 三个容易混淆的概念高度、深度、直径很多人一看到二叉树的直径脑子里第一个反应是“这不就是树的高度吗”这俩确实有关系但完全是两个东西。先说高度。二叉树的高度通常定义为从根节点到最远叶子节点的节点数或边数。递归写法里空节点返回0非空节点返回左右子树最大高度加1这是大家最熟悉的模板。深度则是指从根节点到某个节点的边数或层数是自上而下定义的。直径不一样。直径是任意两个节点之间最长路径的长度这个“任意”两个字是关键。两个节点可以是根节点和某个叶子也可以是左子树最深的叶子和右子树最深的叶子还可以是同一个子树内部的两个节点。换句话说直径描述的是整棵树里最远的一对节点隔了多远。用生活场景打个比方如果说树的高度是“从树顶到最远树梢的距离”那么直径就是“这棵树横向最宽处的跨度”。这两个值经常不一样尤其当树长得不对称的时候。1.2 核心难点最长路径可能不经过根节点新手最常见的错误就是认为二叉树的直径一定等于“左子树高度 右子树高度”。这个结论只有在最长路径恰好经过根节点时才成立。举个例子。假设一棵树是根节点挂了一条很长的左链左链末端又分叉出两个叶子节点而右子树只有孤零零的一个节点。这种情况下最远的两个节点大概率在左子树的内部它们之间的路径根本不需要经过根节点。如果只算“左高右高”结果会是左子树的深度加上右子树的1完全不是真实直径。这就是这道题第一个要扭转思维的地方你要求的是整棵树中任意路径的最大值而不是某一条固定经过根节点的路径。既然路径可能出现在任何子树里那你就必须把每个节点都当作“路径的拐点”来检查一遍。2. 破题思路把大问题拆成每个节点的“拐点贡献”2.1 为什么选择自底向上的后序遍历树的题优先想递归。但直径问题不能从根节点开始向下算因为根节点根本不知道子树内部最远路径有多长。反过来如果你从叶子节点开始让每个节点都向父节点汇报“我这边能向下延伸多深”父节点就有能力把左右两侧的深度拼接成一条经过自己的路径。这个信息流动方向正好对应二叉树的后序遍历先递归处理左子树再递归处理右子树最后处理当前节点。等当前节点拿到左右子树的返回结果时左右子树内部的深度信息已经完全计算完毕。2.2 经过某个节点的最长路径怎么算假设当前节点为 node它的左子树能向下延伸的最大深度是 L右子树能向下延伸的最大深度是 R。那么经过 node 本身、且以 node 为“最高点”的路径长度就是 L R。注意这里 L 和 R 的定义是“从 node 的左孩子出发一路向下能走多少条边”不是左子树的高度也不是节点个数。为什么是相加而不是取最大值因为路径要想经过 node必然要从 node 的左侧某个节点一路向上走到 node再从 node 一路向下走到右侧某个节点把两端的深度拼起来。如果最远路径不经过 node那它一定在左子树或右子树内部已经被递归过程提前记录过了。于是解题思路就清晰了遍历每一个节点计算“左子树深度 右子树深度”用一个全局变量记录这个值的最大值。遍历结束后这个全局变量就是整棵树的直径。2.3 递归返回值设计的艺术这是整个实现里最容易出问题的地方。递归函数到底应该返回什么我见过不少人试图让递归函数直接返回“以当前节点为起点的最长路径长度”然后父节点把左右子树的这个返回值相加。这个想法看着合理但细想就会发现信息不够用。因为父节点拼接路径时需要的不是“子节点内部的最长路径”而是“从子节点往下能延伸到的最远距离”。这两个数值完全不同。正确设计是递归函数返回“当前节点的最大深度”也就是从当前节点出发一路向下最多能走多少条边。这个值等于 max(左子树深度, 右子树深度) 1。而“经过当前节点的最长路径”则在这个返回动作发生之前先用全局变量单独收集。递归返回值是给父节点用的全局变量是给最终答案用的两者各司其职互不干扰。3. 代码实现与逐步拆解3.1 参考实现Python版本先给出完整可运行的代码然后逐行解释。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def diameterOfBinaryTree(self, root: TreeNode) - int: self.ans 0 def dfs(node): # 空节点没有深度返回0 if not node: return 0 # 后序遍历先递归左子树、右子树 left_depth dfs(node.left) right_depth dfs(node.right) # 经过当前节点的最长路径边数是左深度右深度 self.ans max(self.ans, left_depth right_depth) # 返回给父节点的是当前子树的最大深度 return max(left_depth, right_depth) 1 dfs(root) return self.ans代码总共不到二十行核心就是后序遍历加一个全局变量。self.ans负责收集答案初始值为0。dfs函数是核心逻辑先递归左子树拿到左深度再递归右子树拿到右深度然后立刻用left_depth right_depth更新答案。最后返回max(left_depth, right_depth) 1这个返回值代表“从当前节点往下能走的最远边数”。3.2 参考实现Java版本如果你日常写Java模板套路是一样的只是全局变量要放在类的成员位置。class Solution { private int ans 0; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node) { if (node null) { return 0; } int leftDepth dfs(node.left); int rightDepth dfs(node.right); ans Math.max(ans, leftDepth rightDepth); return Math.max(leftDepth, rightDepth) 1; } }Java版本唯一的坑点是成员变量复用的问题。如果你的Solution实例会在多个测试用例之间复用ans必须在每次diameterOfBinaryTree调用开始时重置。刷题平台上每个测试用例通常都会新建一个Solution对象所以一般不会出问题但如果你在本地测试时同一个对象连续调用多次就可能会得到错误结果。3.3 边界情况逐一验证边界情况是考察代码正确性的试金石这道题的边界情况主要有这么几类。第一空树。root为null时dfs直接返回0ans保持初始值0最终返回0。逻辑正确没有空指针问题。第二只有一个节点。根节点的左子树和右子树都是空left_depth和right_depth都是0ans被更新为0函数返回max(0, 0) 1 1。但注意最终返回的答案是ans也就是0。单节点树没有边直径确实是0。第三一条链状树。比如一直往左延伸的链表结构。这种情况下递归深度等于节点数左子树始终有值右子树为空每个节点的left_depth right_depth都等于左侧子树的深度最大值是链上倒数第二个节点处的距离最终结果等于节点数减1也就是最长的那条边数。第四完全二叉树。左右子树都有且比较对称。此时最大路径大概率经过根节点left_depth right_depth会等于左右子树高度之和结果符合直觉。3.4 复杂度分析为什么单次遍历就够时间复杂度是 O(n)n 是节点总数。每个节点在递归过程中恰好被访问一次执行常数次基本操作。空间复杂度是 O(h)h 是树的高度也就是递归调用栈的最大深度。最坏情况下树退化成一条链递归深度为 n空间复杂度 O(n)最好情况下是平衡二叉树递归深度为 log n。有些读者可能会问能不能不用递归理论上可以用显式栈模拟后序遍历但代码复杂度会显著上升。递归的写法足够清晰面试时使用完全没问题只要你能解释清楚调用栈的空间消耗即可。4. 高频易错点与排查思路4.1 踩坑一把直径当成“左高右高”直接返回这是最经典的错误。有人写出这样的代码def diameterOfBinaryTree(self, root): if not root: return 0 return self.maxDepth(root.left) self.maxDepth(root.right)这种写法的问题很明显它只计算了经过根节点的路径完全忽略了最长路径可能在某个子树内部的情况。比如一条单链树根节点只有左子树没有右子树按这个公式算出来就是0 0 0但真实直径应该是链的长度减1。如果非要用“根节点为中心”的思维来解就必须对每个节点都做一次同样的计算并取最大值那就要嵌套递归时间复杂度变成 O(n²)。这是完全可以避免的自底向上的单次遍历就能解决。4.2 踩坑二递归返回值混淆“最大深度”和“最长路径”有人会把递归函数设计成返回“以当前节点为端点的最长路径长度”然后在父节点处把左右返回值相加。听起来和正确版本差不多但实际跑起来会发现结果经常偏大或偏小。关键在于父节点拼接路径时需要知道的是“从子节点往下还能延伸多深”而不是“子节点内部的某条最长路径”。如果返回的是后者这个数值往往比深度大相加出来的路径长度会虚高甚至可能把同一条路径上的节点重复统计。正确逻辑只有一种返回值 当前节点的最大深度答案收集器 左深度 右深度。这两个量级不同千万别混。4.3 踩坑三全局变量的更新时机和位置在递归里更新全局变量时机非常讲究。正确做法是先递归拿到左右子树的深度再更新全局变量最后返回当前深度。如果把ans max(ans, left_depth right_depth)放在了递归调用之前或者放在了return语句之后都会导致结果更新不及时或干脆不更新。放在递归之前此时左右深度还是未计算的初始值或错误值放在return之后这一行代码根本不会执行到。另外有些语言里全局变量如果不在入口处重置连续调用多次就会出错。稳妥的做法是把ans作为成员变量并在主函数入口归零或者用长度为1的数组/可变对象封装答案在递归内部更新。4.4 踩坑四混淆边数和节点数题目说“路径长度”的时候不同的变体定义不同。多数情况下二叉树的直径定义为边的数量比如三个节点的链直径是2。但也有少数题目会把路径长度定义成经过的节点数量那么三个节点的链直径就是3。这个差异直接影响答案的初始值和边界处理。按边数定义单节点树的直径是0空树也是0按节点数定义单节点树的直径是1。写代码之前先确认好定义否则差1的问题会让你调半天。我习惯在本地自测时同时写两个版本的测例空树、单节点、三节点链、五节点二叉树这样四种边界一跑差1问题立刻暴露。4.5 易错点速查表现象可能原因解决方法输出等于左高右高但答案偏小只考虑了经过根节点的路径遍历所有节点全局收集答案答案比真实值大返回值语义混用了路径长度和深度递归返回值统一为当前子树最大深度单节点树输出1混淆边数和节点数根据题目定义调整初始值和返回值逻辑同一对象多次调用结果越来越大全局变量未重置主入口处重置答案变量深度特别大的树栈溢出递归深度过大考虑用迭代栈模拟后序遍历5. 延伸思考同一个模型能解决哪些变体5.1 变体一按节点数计算的直径有些题目把直径定义为路径上的节点数。此时最终答案需要额外加1因为经过某个节点的路径节点数是“边数1”。实现上递归返回值和更新逻辑不用改只在最终返回时处理。比如上面代码最后一行如果是节点数定义就返回self.ans 1。但要注意空树和单节点树的初始答案也要相应调整否则边界会差1。5.2 变体二带权树的直径如果树的边带上权重要求找一条路径使边权之和最大思路依然成立。递归返回“从当前节点向下能获得的最大带权深度”更新答案时改成left_weight right_weight。但这里有个额外的条件如果某个子树的带权深度是负数就不如不选这条路径此时需要用max(0, child_weight)来截断负贡献。这个处理方式很像另一个经典问题——二叉树中的最大路径和。那道题要求节点值相加如果节点值为负数同样需要用截断策略。掌握了直径问题的自底向上框架最大路径和的代码只是把“深度”换成“路径和”把“1”换成“node.val”把“累加边数”换成“累加节点值”模型完全一致。5.3 变体三多叉树的直径从二叉树推广到多叉树问题依然成立。思路不变只是每个节点要维护“所有孩子中的最大深度和次大深度”然后最大 次大就是经过该节点的候选直径。需要注意的是多叉树不能用简单的left right因为孩子数量可能不止两个。这个变体在真实业务场景中很常见。比如分析公司组织架构中两级下属之间的“距离”、分析目录树中两个文件之间的路径层级等本质上都在求树的直径。理解二叉树的解法后多叉树只需要额外维护一个最大和次大的状态代码反而更容易。5.4 相关经典问题串联回顾二叉树的直径、二叉树的最大路径和、二叉树的最大深度、平衡二叉树判断这四个问题共享同一套后序遍历框架。最大深度问题的递归返回值就是直径问题里用到的“深度”平衡二叉树判断要求每个节点的左右子树高度差不超过1一样需要后序遍历同时返回高度最大路径和需要返回“单侧最大增益”同样用全局变量收集答案。把这四道题放在一起对比刷你很快就能体会到为什么说“树的递归题套路是相通的”。6. 实战心得与建议拿这个题练手的时候我建议你不要直接背代码。先自己在草稿纸上画几棵树尤其画那种右边只有一个节点、左边挂一串链的非对称树手动推一遍递归过程体会一下为什么全局变量能在子树内部“截获”答案。我自己第一次写这个题的时候犯过最傻的错误是把ans的更新写在了return的后面。Python 语法上不会报错但那一行永远不会执行输出永远是0。排查了五分钟才意识到是执行顺序问题。这种错误很隐性光看代码看不出毛病必须动手调试才能发现。所以遇到结果不对别急着怀疑公式先把“更新”和“返回”的先后顺序捋一遍。到了面试场景不要一上来就写代码。先跟面试官确认一个关键定义“直径算的是边数还是节点数”这个问题一出口对方就知道你对边界情况有意识。然后讲思路后序遍历每个节点处用左深度加右深度更新全局答案递归返回最大深度。把这三句话说清楚比闷头写十行代码效果好得多。最后一个实用技巧本地自测时把树的构造和输出封装成两个简单函数批量跑空树、单节点、三节点链、非对称树四个用例。这套用例跑通了代码基本就稳了。刷题不是比谁记得模板多而是比谁对边界和原理理解得透这道39题正好是个试金石。
