先问一个问题刷LeetCode的时候你是“看题五分钟、看答案两小时”的类型还是那种把每道题当成一次底层逻辑训练、非得把递归调用栈在脑子里跑完才肯罢休的类型实话讲第543题《二叉树的直径》属于前者看起来很简单、后者越品越有味道的典型。它被收录在LeetCode热门100题里也在很多大厂笔试的高频清单里占着位置。作为Day 14的刷题任务这道题表面上只要求“求一棵树中任意两个节点路径长度的最大值”但真正动手用JavaScript写的时候很多人会卡在一个地方为什么我递归返回的是高度但答案却在另一个变量里累加今天我把这道题从题意、思路、代码到踩坑完整拆开讲一遍希望你看完不只是会AC而是下次遇到任何“遍历过程中收集某种全局信息”的题目都能顺手拿捏。这道题适合谁适合正在按题单刷二叉树基础的人也适合准备面试、想弄明白“树的dfs到底在每一层做了什么”的人。我会把递归的每一层展开讲清楚代码也全部用JavaScript写你复制到LeetCode里就能跑。1. 题目到底在问什么——别再被“直径”两个字带偏1.1 先看懂题面原文LeetCode 543的原题描述不长给定一棵二叉树你需要计算它的直径长度。一棵二叉树的直径长度是任意两个节点路径中路径边数的最大值。注意这条路径可能穿过也可能不穿过根节点。很多初学者第一步就被“直径”这个几何词汇唬住了以为要像算圆的直径一样找到树的中心然后量两端的距离。其实二叉树的“直径”一点都不高深翻译成人话就是在这棵树的所有节点对之间找到距离最远的那一对计算它们之间有多少条边。这里的“边数”很关键如果你按“经过了多少个节点”去数就会比正确答案多1。1.2 生活类比把树想成一张地铁图假如你把这棵二叉树想成一张地铁线路图每个节点是一个站每条连接父子节点的引用是一条线路。那二叉树的直径就是这棵树里“从某一个站到另一个站坐得最远的一条路线”要经过多少个区间。普通的地铁图线路是直的而树的连接方式是分叉的所以这条“最远路线”一定是由某个节点出发、往左下方走一段、再往右下方走一段组成的。换句话说任何一条树内路径都可以看成在以某个节点为“拐点”的地方向下弯折而成。这个视角非常重要。它意味着要算全局最长的路径不需要去比较任意两个叶子节点之间的距离只需要遍历每一个节点把这个节点“左侧能往下走多深”和“右侧能往下走多深”加起来取一个最大值就行。你可能会问为什么不考虑拐点不在当前节点的情况因为每一条路径必然有唯一一个“最高点”也就是这条路径上离根最近的那个节点专业说法叫LCA最近公共祖先这个最高点就是拐点。所以枚举每一个节点当拐点一定不会漏掉任何候选路径。1.3 这题真正考的是“后序遍历的副产物”LeetCode 543的题解区一眼扫过去十个里有八个是十几行的递归。但你要清楚这道题表面上在考“树的遍历”深层其实在考一件事你能否设计一个递归函数让它在返回“高度”这个主结果的同时悄悄对外部变量产生副作用最终由这个副作用拼出真正想要的答案。常规的层序遍历、前序遍历解决不了这个问题。因为你在遍历到某个节点时根本不知道它左右子树的最大深度非要先探到底再回头算。而后续遍历天然满足这个需求先算完左子树、右子树回到当前节点时左右两边的信息都已经齐了此时立即更新答案再把自己这层的“高度”返回给父节点。这个“边返回边更新”的模式是这道题的灵魂也是之后做当时最大路径和、验证平衡二叉树等一堆题目时反复出现的套路。2. 解题思路拆解从暴力递归到单次遍历2.1 第一反应遍历每个节点分别求两侧高度先想一个最笨但绝对正确的办法。直径等于某个节点左右子树高度之和的最大值那我可以先写一个工具函数输入一个节点返回这棵子树的最大高度这是任何学过二叉树的人都会的递归。然后在主函数里再来一层递归遍历每一个节点每到一处就调用工具函数算左高度、算右高度加加看不断更新最大值。这个思路逻辑完全正确复杂度也能过因为树总共就N个节点每个节点调用一次工具函数工具函数本身又要遍历以该节点为根的整棵子树因此总时间复杂度是O(N²)。LeetCode的数据量下不算太差有些语言能勉强AC但这不是一个合格解法。更关键的是它暴露一个问题同一棵子树的高度被反复计算了无数次底层叶子节点甚至被访问了几十遍这种重复劳动在递归里是完全可以避免的。2.2 双递归的致命伤重复计算具体想一个极端情况一棵退化成链状的树每个节点只有一个左孩子。用双递归的思路跑一遍根节点算左子树高度要一路走到底N步接着左孩子作为新的主遍历节点又要从自己往下走到底N-1步…全部加起来是O(N²)的量级。LeetCode上N达到10的4次方时这个复杂度虽然可能勉强跑完但肯定谈不上优雅。而任何一个稍微有点经验的工程师都会意识到计算某个节点的高度本质依赖它孩子节点的高度我完全可以在一次自底向上的遍历中把每个节点的高度都算出来并缓存。这里的“缓存”不需要额外开Map直接把信息存储在递归返回值里就是最自然的缓存。每个节点的高度只算一次整体退化到O(N)。2.3 优化思路一次DFS等子树信息齐了再更新答案单次DFS的核心设计是这样的定义一个递归函数它返回以当前节点为根的子树的最大高度。在函数内部先递归地拿到左孩子的高度和右孩子的高度这两个值都拿到了当前节点作为拐点的最长路径就是“左孩子高度 右孩子高度”拿这个值去更新全局答案。最后当前节点返回给父节点的高度是“左右孩子中更高的那一个 1加上当前节点自身这一层”。这个设计里有一个需要反复消化的点一个节点返回给父节点的值和它用来更新答案的值不是同一个东西。更新答案用的是“左高度 右高度”因为路径从当前节点左子树最深处一路到右子树最深处拐点处不需要再加当前节点本身的边返回给父节点用的是“max(左高度, 右高度) 1”因为父节点未来要沿着这条侧继续往下延伸时只能选择更高的一条分支继续走不能左右两边都占着。理解了这个差别代码就只是一层窗户纸的事。为什么只选高的那一条因为路径是线性的一个节点向上走时不可能同时走上左子树和右子树。就像一个电梯到了某一层你只能选择向左走还是向右走不可能同时跨两条走廊所以给父节点的高度只能是单侧最大深度再加当前这一层。3. JavaScript实现完整代码与逐行解读3.1 完整代码先睹为快直接看最终解法JavaScript版本全部代码不到20行var diameterOfBinaryTree function(root) { let ans 0; const dfs (node) { if (!node) return 0; const leftDepth dfs(node.left); const rightDepth dfs(node.right); ans Math.max(ans, leftDepth rightDepth); return Math.max(leftDepth, rightDepth) 1; }; dfs(root); return ans; };提交到LeetCode上时间复杂度O(N)空间复杂度O(H)H是树的高度最坏情况下链状树是O(N)但一般不用特别纠结。3.2 为什么递归函数要“干两件事”注意看dfs这个函数的职责它其实同时干了两件事。第一件事计算并返回以node为根的子树高这是它对外部也不言而喻的语义第二件事在计算过程中顺手检查“如果以node作为拐点直径候选值是多少”并更新外部变量ans。这个设计有点像一个工程团队里产品经理让程序员去统计页面访问量程序员统计的同时顺手把一个隐藏的bug日志也采了回来。返回值是主任务修改ans是副产物两者不冲突反而共用了同一次递归遍历的全部信息。为什么必须用外部变量因为dfs的返回值已经用于表达“子树高度”这个语义不能再同时表达“直径”。如果你试图让一个函数同时返回高度和答案语法上需要另开一个对象或者数组来打包反而啰嗦。用一个闭包变量ans记录全局最优值是这类题目的标准做法简洁、高效、可读性好。3.3 边界条件与base case递归第一步判断节点是否为空。如果是null直接返回0。这个0代表“空子树的高度是0”它没有子节点自然也不可能贡献任何深度。这里稍微注意一下有些人喜欢用“空节点返回-1”的写法那通常是用在计算“经过节点的数量”或者处理平衡树时这道题计算的是边数空节点的高度用0最贴合题意。树只有单个节点时左右孩子都是空leftDepth和rightDepth都是0ans更新为0 0 0返回0。而single节点的直径确实就是0因为从自己到自己不算路径没有边。这个边界情况很容易被忽略但LeetCode的测试用例里必然有写代码的时候先把这层想通后面的逻辑就顺了。4. 这题真正的难点思维陷阱与常见错误4.1 陷阱一更新答案时要不要加1这是评论区里最常见的争论。有些人的代码是ans Math.max(ans, left right)有些人的是ans Math.max(ans, left right 1)。为什么前一种才是对的因为left和right代表的是左右子树各自的最大高度也就是从当前节点的左孩子往下走到最深处经过的边数。当路径以当前节点为拐点时它从当前节点出发先往左走到左子树最底部这段的边数是left再回到当前节点往右走到右子树最底部这段的边数是right。两段路径以当前节点为连接点中间没有额外的边需要算所以总长度就是left right不需要再加1。而如果你用的是“左高度 右高度 1”那就相当于多算了一条边本来应该是5的直径你输出6。什么时候需要加1一些题解里提到的“节点数量”版本。如果题目把直径定义成“路径经过的节点数”那确实要在边数上加1。但LeetCode 543题干白纸黑字写的是“路径边数的最大值”所以别被其他语言的题解带偏认准你的left和right都是高度边数答案就直接相加。4.2 陷阱二递归返回时加1忘了算当前节点与陷阱一相反返回给父节点的值必须在左右高度的最大值上再加1。为什么要加因为父节点如果要经过当前节点继续往下走当前节点本身也是路径上的一层。试想一棵只有左孩子的简单树根节点的左子树高度是0左孩子是空那么根节点的高度应该是1还是0按照二叉树的高度定义只有一个节点的树高度为0还是1取决于约定但在这道题的递归里我们必须把“当前节点本身”算作这一层的贡献否则父节点计算高度时就会漏算节点数导致最终的直径少算。我用一个具体例子验证根节点A有一个左孩子BB没有孩子。真实直径是1A到B的一条边。跑代码的时候B节点的dfs返回 max(0,0)1 1这是B子树的高度。回到A节点leftDepth 1rightDepth 0ans更新为1符合预期。如果你在返回的时候漏写了1leftDepth就是0ans算出来0直接错。4.3 陷阱三把整棵树的全局变量放在递归里赋值JavaScript的闭包特性让外部变量在递归函数里修改非常自然但也带来一些隐性问题。如果你把ans定义在diameterOfBinaryTree内部、dfs外部那么每次执行这个函数时ans都会重新初始化为0没问题。但假如你不小心把ans定义在了模块的顶层、或者在类里定义成了静态属性那LeetCode多次调用测试用例时上一次残留的值就会污染下一次的计算导致结果错误。这个问题在本地调试时很难发现因为你在同一个页面反复跑同一个用例每次都能复现但提交上去换了测试环境就会偶发错误。建议养成习惯所有需要用到的全局变量一律放在主函数内部声明用闭包去捕获别往外层作用域扩散。4.4 时间复杂度与空间复杂度自查复杂度这点必须做到脱口而出。时间上每个节点恰好访问一次在节点内部做两次递归调用和一次Math.max都是常数时间总复杂度O(N)。空间上递归栈的深度等于树的高度最坏情况是一棵严重偏斜的树高度为N所以空间O(N)平均情况一棵比较平衡的树空间O(log N)。面试时如果被追问“能不能用迭代实现”答案是可以用栈模拟后序遍历但由于需要记录每个节点返回的高度代码会明显变长通常没有必要递归是这道题最自然的解法。5. 变式与延展会这一题等于会一大片题目5.1 兄弟题二叉树的最大路径和LeetCode 124LeetCode 124是这道题最经典的进化版。同样是遍历每个节点作为拐点同样在递归返回值里携带单侧最大信息区别在于节点上带了权值正负都可能路径计算的是节点值的总和而且路径可以只停在任意节点不一定要走到叶子。对比着看很有意思124题中如果子树的单侧路径和是负数那它对上层节点来说就是累赘不如直接截断把当前节点的返回值变成只包含当前节点本身的值而在543题里高度永远是正数不存在“某个分支我不想要了”这种情况。理解了两者的差异你对“递归过程中怎么筛选有效信息”的理解会上升一层。5.2 兄弟题验证平衡二叉树LeetCode 110平衡二叉树的定义是每个节点的左右子树高度差不超过1。又是一个类似的递归模式后序遍历拿到左右子树高度然后一比较超过1就标记为false。很多人的第一步想法是写两个函数一个查高度一个遍历判断又回到O(N²)的老路。会了543之后你应该自然想到把“高度”和“是否平衡”两类信息在一次DFS中合并处理可以通过返回-1标记不平衡也可以用外部变量提前终止。5.3 跟前端工程化的挂钩DOM树也能这样算如果你觉得这些二叉树题目离实际开发太远不妨想想前端的一个常见需求统计页面中某个组件的最大嵌套深度。DOM本身是一棵多叉树但递归遍历的逻辑一模一样。LeetCode 543练出来的“后序遍历 返回值 外部最大值”的模式几乎可以原封不动地用在处理React组件嵌套层级、计算CSS选择器的最大深度、甚至递归分析JSON对象的最大嵌套层数上。学好递归的后序返回模式你在工作中处理任何“树形结构数据”都会比别人快一步。5.4 如果再往前走一步换语言写法差别在哪很多朋友学的第一门语言不是JavaScript做题时喜欢先看Python或者Java的题解再翻译成JS。这个过程容易踩坑Python的递归返回值可以直接用元组(depth, max_diameter)打包而JS里这么写反而别扭不如用外部变量干净Java的类成员变量和实例方法也能改但要注意清空状态。JavaScript的优势在于闭包天然配合这类问题在函数内部声明一个变量递归函数里随便改不会污染外部环境这也是我推荐JS用户直接采用“返回值 外部变量”方案的原因。6. 调试小技巧再小的题也有值得记录的经验6.1 手动画出递归调用栈跑一遍我刚学这题的时候先别急着提交找张草稿纸画一棵3层二叉树把dfs的每一步调用栈写出来。重点看两个时刻第一个时刻是某个节点拿到了左右子树的返回值但还没更新ans的时候第二个时刻是它把单侧最大深度返回给父节点的时候。把这两个时刻的值盯着写清楚整道题的逻辑就永远长在你脑子里了比背十遍代码管用。6.2 用一个自测用例验证边界至少用三组数据自测空树返回0单节点返回0三个节点的完全二叉树根节点左右各一个叶子此时越来越容易错——左右子树高度都是1ans更新为2正确答案就是2。再测一个链状树比如1-2-3-4的右链直径应该是3看代码能不能自动算对。LeetCode支持自定义测试用例建议把这些用例全跑一遍再提交。6.3 警惕“看着能跑换个用例就崩”的幻觉JavaScript是一种宽容的语言很多错误不会在运行时立刻暴露。比如Math.max()里有一个参数是undefined结果不会立刻报错只会变成NaN然后整个ans一路NaN到底最后输出null——这种错最难查。所以递归头部的空值判断一定要写得严谨别用node.left这种不考虑空的写法实际上我们是用递归函数时自动处理了null确保每个访问属性的地方前面都有安全判断。7. Day 14刷题计划的复盘这道题在题单里的位置如果你是按LeetCode热门100题的题单刷到第14天你会发现前面的题目大多是数组、链表这些线性结构到了第543题难度并没有陡增但思维上第一次要求你跳脱“单线程遍历”开始适应“遍历过程中同时收集另一份信息”的模式。这个转折点相当关键它既是二叉树系列的入门题之一也是之后遇到任何“边遍历边求最值”问题的思维基石。我个人在刷题计划里的习惯是每道题AC之后做三件事第一把官方题解的思路原文读一遍重点看它为什么不用双递归第二去讨论区翻一翻别人贴出的错误代码看最容易踩的坑是否和自己想的一样第三在代码注释里写一句“这道题为什么返回值不等于答案的说明”。这三个动作坚持下来十天之后你对树的递归题会有一种近乎条件反射的直觉——看到“任意路径”“最远”“最大和”这类词脑子里会自动弹出“拐点 后序 外部变量”的框架。这道题如果只看表面20行代码花两分钟就能背完。但如果你把“递归返回单侧信息同时用一个全局变量记录当前最优值”的模式彻底消化了它帮你在后续的更多问题里省下的时间远比这一道题本身多得多。这是经验之谈信不信你刷到LeetCode 437或者124的时候自然会有体会。 
长河君 · 2026/10/11 7:22:07 · 阅读 1.2k LeetCode 543：二叉树直径的JavaScript递归解法详解
先问一个问题刷LeetCode的时候你是“看题五分钟、看答案两小时”的类型还是那种把每道题当成一次底层逻辑训练、非得把递归调用栈在脑子里跑完才肯罢休的类型实话讲第543题《二叉树的直径》属于前者看起来很简单、后者越品越有味道的典型。它被收录在LeetCode热门100题里也在很多大厂笔试的高频清单里占着位置。作为Day 14的刷题任务这道题表面上只要求“求一棵树中任意两个节点路径长度的最大值”但真正动手用JavaScript写的时候很多人会卡在一个地方为什么我递归返回的是高度但答案却在另一个变量里累加今天我把这道题从题意、思路、代码到踩坑完整拆开讲一遍希望你看完不只是会AC而是下次遇到任何“遍历过程中收集某种全局信息”的题目都能顺手拿捏。这道题适合谁适合正在按题单刷二叉树基础的人也适合准备面试、想弄明白“树的dfs到底在每一层做了什么”的人。我会把递归的每一层展开讲清楚代码也全部用JavaScript写你复制到LeetCode里就能跑。1. 题目到底在问什么——别再被“直径”两个字带偏1.1 先看懂题面原文LeetCode 543的原题描述不长给定一棵二叉树你需要计算它的直径长度。一棵二叉树的直径长度是任意两个节点路径中路径边数的最大值。注意这条路径可能穿过也可能不穿过根节点。很多初学者第一步就被“直径”这个几何词汇唬住了以为要像算圆的直径一样找到树的中心然后量两端的距离。其实二叉树的“直径”一点都不高深翻译成人话就是在这棵树的所有节点对之间找到距离最远的那一对计算它们之间有多少条边。这里的“边数”很关键如果你按“经过了多少个节点”去数就会比正确答案多1。1.2 生活类比把树想成一张地铁图假如你把这棵二叉树想成一张地铁线路图每个节点是一个站每条连接父子节点的引用是一条线路。那二叉树的直径就是这棵树里“从某一个站到另一个站坐得最远的一条路线”要经过多少个区间。普通的地铁图线路是直的而树的连接方式是分叉的所以这条“最远路线”一定是由某个节点出发、往左下方走一段、再往右下方走一段组成的。换句话说任何一条树内路径都可以看成在以某个节点为“拐点”的地方向下弯折而成。这个视角非常重要。它意味着要算全局最长的路径不需要去比较任意两个叶子节点之间的距离只需要遍历每一个节点把这个节点“左侧能往下走多深”和“右侧能往下走多深”加起来取一个最大值就行。你可能会问为什么不考虑拐点不在当前节点的情况因为每一条路径必然有唯一一个“最高点”也就是这条路径上离根最近的那个节点专业说法叫LCA最近公共祖先这个最高点就是拐点。所以枚举每一个节点当拐点一定不会漏掉任何候选路径。1.3 这题真正考的是“后序遍历的副产物”LeetCode 543的题解区一眼扫过去十个里有八个是十几行的递归。但你要清楚这道题表面上在考“树的遍历”深层其实在考一件事你能否设计一个递归函数让它在返回“高度”这个主结果的同时悄悄对外部变量产生副作用最终由这个副作用拼出真正想要的答案。常规的层序遍历、前序遍历解决不了这个问题。因为你在遍历到某个节点时根本不知道它左右子树的最大深度非要先探到底再回头算。而后续遍历天然满足这个需求先算完左子树、右子树回到当前节点时左右两边的信息都已经齐了此时立即更新答案再把自己这层的“高度”返回给父节点。这个“边返回边更新”的模式是这道题的灵魂也是之后做当时最大路径和、验证平衡二叉树等一堆题目时反复出现的套路。2. 解题思路拆解从暴力递归到单次遍历2.1 第一反应遍历每个节点分别求两侧高度先想一个最笨但绝对正确的办法。直径等于某个节点左右子树高度之和的最大值那我可以先写一个工具函数输入一个节点返回这棵子树的最大高度这是任何学过二叉树的人都会的递归。然后在主函数里再来一层递归遍历每一个节点每到一处就调用工具函数算左高度、算右高度加加看不断更新最大值。这个思路逻辑完全正确复杂度也能过因为树总共就N个节点每个节点调用一次工具函数工具函数本身又要遍历以该节点为根的整棵子树因此总时间复杂度是O(N²)。LeetCode的数据量下不算太差有些语言能勉强AC但这不是一个合格解法。更关键的是它暴露一个问题同一棵子树的高度被反复计算了无数次底层叶子节点甚至被访问了几十遍这种重复劳动在递归里是完全可以避免的。2.2 双递归的致命伤重复计算具体想一个极端情况一棵退化成链状的树每个节点只有一个左孩子。用双递归的思路跑一遍根节点算左子树高度要一路走到底N步接着左孩子作为新的主遍历节点又要从自己往下走到底N-1步…全部加起来是O(N²)的量级。LeetCode上N达到10的4次方时这个复杂度虽然可能勉强跑完但肯定谈不上优雅。而任何一个稍微有点经验的工程师都会意识到计算某个节点的高度本质依赖它孩子节点的高度我完全可以在一次自底向上的遍历中把每个节点的高度都算出来并缓存。这里的“缓存”不需要额外开Map直接把信息存储在递归返回值里就是最自然的缓存。每个节点的高度只算一次整体退化到O(N)。2.3 优化思路一次DFS等子树信息齐了再更新答案单次DFS的核心设计是这样的定义一个递归函数它返回以当前节点为根的子树的最大高度。在函数内部先递归地拿到左孩子的高度和右孩子的高度这两个值都拿到了当前节点作为拐点的最长路径就是“左孩子高度 右孩子高度”拿这个值去更新全局答案。最后当前节点返回给父节点的高度是“左右孩子中更高的那一个 1加上当前节点自身这一层”。这个设计里有一个需要反复消化的点一个节点返回给父节点的值和它用来更新答案的值不是同一个东西。更新答案用的是“左高度 右高度”因为路径从当前节点左子树最深处一路到右子树最深处拐点处不需要再加当前节点本身的边返回给父节点用的是“max(左高度, 右高度) 1”因为父节点未来要沿着这条侧继续往下延伸时只能选择更高的一条分支继续走不能左右两边都占着。理解了这个差别代码就只是一层窗户纸的事。为什么只选高的那一条因为路径是线性的一个节点向上走时不可能同时走上左子树和右子树。就像一个电梯到了某一层你只能选择向左走还是向右走不可能同时跨两条走廊所以给父节点的高度只能是单侧最大深度再加当前这一层。3. JavaScript实现完整代码与逐行解读3.1 完整代码先睹为快直接看最终解法JavaScript版本全部代码不到20行var diameterOfBinaryTree function(root) { let ans 0; const dfs (node) { if (!node) return 0; const leftDepth dfs(node.left); const rightDepth dfs(node.right); ans Math.max(ans, leftDepth rightDepth); return Math.max(leftDepth, rightDepth) 1; }; dfs(root); return ans; };提交到LeetCode上时间复杂度O(N)空间复杂度O(H)H是树的高度最坏情况下链状树是O(N)但一般不用特别纠结。3.2 为什么递归函数要“干两件事”注意看dfs这个函数的职责它其实同时干了两件事。第一件事计算并返回以node为根的子树高这是它对外部也不言而喻的语义第二件事在计算过程中顺手检查“如果以node作为拐点直径候选值是多少”并更新外部变量ans。这个设计有点像一个工程团队里产品经理让程序员去统计页面访问量程序员统计的同时顺手把一个隐藏的bug日志也采了回来。返回值是主任务修改ans是副产物两者不冲突反而共用了同一次递归遍历的全部信息。为什么必须用外部变量因为dfs的返回值已经用于表达“子树高度”这个语义不能再同时表达“直径”。如果你试图让一个函数同时返回高度和答案语法上需要另开一个对象或者数组来打包反而啰嗦。用一个闭包变量ans记录全局最优值是这类题目的标准做法简洁、高效、可读性好。3.3 边界条件与base case递归第一步判断节点是否为空。如果是null直接返回0。这个0代表“空子树的高度是0”它没有子节点自然也不可能贡献任何深度。这里稍微注意一下有些人喜欢用“空节点返回-1”的写法那通常是用在计算“经过节点的数量”或者处理平衡树时这道题计算的是边数空节点的高度用0最贴合题意。树只有单个节点时左右孩子都是空leftDepth和rightDepth都是0ans更新为0 0 0返回0。而single节点的直径确实就是0因为从自己到自己不算路径没有边。这个边界情况很容易被忽略但LeetCode的测试用例里必然有写代码的时候先把这层想通后面的逻辑就顺了。4. 这题真正的难点思维陷阱与常见错误4.1 陷阱一更新答案时要不要加1这是评论区里最常见的争论。有些人的代码是ans Math.max(ans, left right)有些人的是ans Math.max(ans, left right 1)。为什么前一种才是对的因为left和right代表的是左右子树各自的最大高度也就是从当前节点的左孩子往下走到最深处经过的边数。当路径以当前节点为拐点时它从当前节点出发先往左走到左子树最底部这段的边数是left再回到当前节点往右走到右子树最底部这段的边数是right。两段路径以当前节点为连接点中间没有额外的边需要算所以总长度就是left right不需要再加1。而如果你用的是“左高度 右高度 1”那就相当于多算了一条边本来应该是5的直径你输出6。什么时候需要加1一些题解里提到的“节点数量”版本。如果题目把直径定义成“路径经过的节点数”那确实要在边数上加1。但LeetCode 543题干白纸黑字写的是“路径边数的最大值”所以别被其他语言的题解带偏认准你的left和right都是高度边数答案就直接相加。4.2 陷阱二递归返回时加1忘了算当前节点与陷阱一相反返回给父节点的值必须在左右高度的最大值上再加1。为什么要加因为父节点如果要经过当前节点继续往下走当前节点本身也是路径上的一层。试想一棵只有左孩子的简单树根节点的左子树高度是0左孩子是空那么根节点的高度应该是1还是0按照二叉树的高度定义只有一个节点的树高度为0还是1取决于约定但在这道题的递归里我们必须把“当前节点本身”算作这一层的贡献否则父节点计算高度时就会漏算节点数导致最终的直径少算。我用一个具体例子验证根节点A有一个左孩子BB没有孩子。真实直径是1A到B的一条边。跑代码的时候B节点的dfs返回 max(0,0)1 1这是B子树的高度。回到A节点leftDepth 1rightDepth 0ans更新为1符合预期。如果你在返回的时候漏写了1leftDepth就是0ans算出来0直接错。4.3 陷阱三把整棵树的全局变量放在递归里赋值JavaScript的闭包特性让外部变量在递归函数里修改非常自然但也带来一些隐性问题。如果你把ans定义在diameterOfBinaryTree内部、dfs外部那么每次执行这个函数时ans都会重新初始化为0没问题。但假如你不小心把ans定义在了模块的顶层、或者在类里定义成了静态属性那LeetCode多次调用测试用例时上一次残留的值就会污染下一次的计算导致结果错误。这个问题在本地调试时很难发现因为你在同一个页面反复跑同一个用例每次都能复现但提交上去换了测试环境就会偶发错误。建议养成习惯所有需要用到的全局变量一律放在主函数内部声明用闭包去捕获别往外层作用域扩散。4.4 时间复杂度与空间复杂度自查复杂度这点必须做到脱口而出。时间上每个节点恰好访问一次在节点内部做两次递归调用和一次Math.max都是常数时间总复杂度O(N)。空间上递归栈的深度等于树的高度最坏情况是一棵严重偏斜的树高度为N所以空间O(N)平均情况一棵比较平衡的树空间O(log N)。面试时如果被追问“能不能用迭代实现”答案是可以用栈模拟后序遍历但由于需要记录每个节点返回的高度代码会明显变长通常没有必要递归是这道题最自然的解法。5. 变式与延展会这一题等于会一大片题目5.1 兄弟题二叉树的最大路径和LeetCode 124LeetCode 124是这道题最经典的进化版。同样是遍历每个节点作为拐点同样在递归返回值里携带单侧最大信息区别在于节点上带了权值正负都可能路径计算的是节点值的总和而且路径可以只停在任意节点不一定要走到叶子。对比着看很有意思124题中如果子树的单侧路径和是负数那它对上层节点来说就是累赘不如直接截断把当前节点的返回值变成只包含当前节点本身的值而在543题里高度永远是正数不存在“某个分支我不想要了”这种情况。理解了两者的差异你对“递归过程中怎么筛选有效信息”的理解会上升一层。5.2 兄弟题验证平衡二叉树LeetCode 110平衡二叉树的定义是每个节点的左右子树高度差不超过1。又是一个类似的递归模式后序遍历拿到左右子树高度然后一比较超过1就标记为false。很多人的第一步想法是写两个函数一个查高度一个遍历判断又回到O(N²)的老路。会了543之后你应该自然想到把“高度”和“是否平衡”两类信息在一次DFS中合并处理可以通过返回-1标记不平衡也可以用外部变量提前终止。5.3 跟前端工程化的挂钩DOM树也能这样算如果你觉得这些二叉树题目离实际开发太远不妨想想前端的一个常见需求统计页面中某个组件的最大嵌套深度。DOM本身是一棵多叉树但递归遍历的逻辑一模一样。LeetCode 543练出来的“后序遍历 返回值 外部最大值”的模式几乎可以原封不动地用在处理React组件嵌套层级、计算CSS选择器的最大深度、甚至递归分析JSON对象的最大嵌套层数上。学好递归的后序返回模式你在工作中处理任何“树形结构数据”都会比别人快一步。5.4 如果再往前走一步换语言写法差别在哪很多朋友学的第一门语言不是JavaScript做题时喜欢先看Python或者Java的题解再翻译成JS。这个过程容易踩坑Python的递归返回值可以直接用元组(depth, max_diameter)打包而JS里这么写反而别扭不如用外部变量干净Java的类成员变量和实例方法也能改但要注意清空状态。JavaScript的优势在于闭包天然配合这类问题在函数内部声明一个变量递归函数里随便改不会污染外部环境这也是我推荐JS用户直接采用“返回值 外部变量”方案的原因。6. 调试小技巧再小的题也有值得记录的经验6.1 手动画出递归调用栈跑一遍我刚学这题的时候先别急着提交找张草稿纸画一棵3层二叉树把dfs的每一步调用栈写出来。重点看两个时刻第一个时刻是某个节点拿到了左右子树的返回值但还没更新ans的时候第二个时刻是它把单侧最大深度返回给父节点的时候。把这两个时刻的值盯着写清楚整道题的逻辑就永远长在你脑子里了比背十遍代码管用。6.2 用一个自测用例验证边界至少用三组数据自测空树返回0单节点返回0三个节点的完全二叉树根节点左右各一个叶子此时越来越容易错——左右子树高度都是1ans更新为2正确答案就是2。再测一个链状树比如1-2-3-4的右链直径应该是3看代码能不能自动算对。LeetCode支持自定义测试用例建议把这些用例全跑一遍再提交。6.3 警惕“看着能跑换个用例就崩”的幻觉JavaScript是一种宽容的语言很多错误不会在运行时立刻暴露。比如Math.max()里有一个参数是undefined结果不会立刻报错只会变成NaN然后整个ans一路NaN到底最后输出null——这种错最难查。所以递归头部的空值判断一定要写得严谨别用node.left这种不考虑空的写法实际上我们是用递归函数时自动处理了null确保每个访问属性的地方前面都有安全判断。7. Day 14刷题计划的复盘这道题在题单里的位置如果你是按LeetCode热门100题的题单刷到第14天你会发现前面的题目大多是数组、链表这些线性结构到了第543题难度并没有陡增但思维上第一次要求你跳脱“单线程遍历”开始适应“遍历过程中同时收集另一份信息”的模式。这个转折点相当关键它既是二叉树系列的入门题之一也是之后遇到任何“边遍历边求最值”问题的思维基石。我个人在刷题计划里的习惯是每道题AC之后做三件事第一把官方题解的思路原文读一遍重点看它为什么不用双递归第二去讨论区翻一翻别人贴出的错误代码看最容易踩的坑是否和自己想的一样第三在代码注释里写一句“这道题为什么返回值不等于答案的说明”。这三个动作坚持下来十天之后你对树的递归题会有一种近乎条件反射的直觉——看到“任意路径”“最远”“最大和”这类词脑子里会自动弹出“拐点 后序 外部变量”的框架。这道题如果只看表面20行代码花两分钟就能背完。但如果你把“递归返回单侧信息同时用一个全局变量记录当前最优值”的模式彻底消化了它帮你在后续的更多问题里省下的时间远比这一道题本身多得多。这是经验之谈信不信你刷到LeetCode 437或者124的时候自然会有体会。