我先说个我自己的真实经历刷到 Leetcode 543 二叉树的直径那天是我连续刷题的第 14 天。当时我脑子里全是二叉树的各种遍历模板看到“直径”两个字第一反应就是——找根节点左右子树的最大深度然后加在一起答案不就出来了吗结果第一次提交就错了。后来我才反应过来这道题最阴的地方恰恰在这里二叉树的直径完全可以不经过根节点。这道题非常适合用来理解“树的路径问题”它表面上是在考遍历实际上考的是你能否把一条任意路径拆成“某个节点左侧一段 右侧一段”。而且这道题用 JavaScript 写起来特别短核心递归逻辑十几行就能讲完。我会从题目定义开始把“为什么不能只算根节点的左右深度”这个坑讲透再给出基于后序遍历的 JavaScript 解法最后用几个边界用例验证一遍再把同一套思路延伸到最大深度、平衡二叉树、最大路径和、最长同值路径这几道高频题上。1. 直径的判定标准题目要的是“边数”不是“经过几个节点”很多第一次做这道题的人连题目定义都没完全看清就去写代码了。Leetcode 543 里说的“直径”是指二叉树中任意两个节点路径长度中的最大值而这个“路径长度”是按边数来算的不是按节点个数来算的。这一点非常关键因为网上不少题解喜欢用“深度”来表示高度一会儿按节点数返回一会儿按边数返回很容易把人绕晕。1.1 示例过一遍4 到 3 为什么算 3原题给的例子是[1,2,3,4,5]树的结构大概是根节点 1左孩子 2右孩子 3节点 2 的左孩子 4右孩子 5要找最长路径可以走4 - 2 - 1 - 3。从 4 到 3中间经过的边有 3 条4-2、2-1、1-3。所以返回值是 3而不是 4。如果你按“路径上经过多少个节点”来理解节点数是 4那就错了。我建议在写代码前先统一自己的口径递归函数里返回的“深度”就是节点数口径空节点返回 0叶子节点返回 1而题目要的“直径”则用左右两棵子树的“深度相加”来表示。因为左子树深度left表示从左端点向上走到当前节点的节点数减一右子树同理两者相加恰好就是经过当前节点的最长边数。这个口径一旦定下来写代码时就不用一会儿加一会儿减。1.2 高度返回值与直径更新值之间的关系这里我多解释一下因为实际面试时特别容易在这里卡壳。假如一个节点只有左子树左子树最大深度是 5右子树为空那经过这个节点的最大路径只能是左子树的某个叶子到这个节点本身边数是 5。此时公式left right就是5 0 5完全没问题。如果左右子树都有比如左右深度分别是 3 和 4从左子树最深的叶子出发经过当前节点再到右子树最深的叶子路径边数是3 4 7。注意这里没有额外加 1因为左右深度本身已经把当前节点到两侧的边都算进去了。用一个生活化的类比你可以把当前节点想象成一个换乘站左边到你出发站要坐 3 站右边到你目的地站要坐 4 站那么全程就是 7 站不需要把换乘站本身再算一次。2. “根左右最大深度之和”为何不够最长路径可以完全绕开根这是我踩过最大的坑也是把这道题从“简单遍历”变成“树形 DP 入门题”的关键。如果你只算maxDepth(root.left) maxDepth(root.right)那相当于默认最长路径一定经过根节点但这个前提根本不成立。2.1 一个不经过根的反例想象一棵树根节点只有一个左孩子但这个左孩子自己有两个很深的孩子节点。更直白一点构造一棵这样的树根节点 1没有右孩子节点 2 是根的唯一左孩子节点 2 有左孩子 4 和右孩子 5节点 4 下面挂一条很深的链节点 5 下面也挂一条很深的链这个时候整棵树里最远的两个叶子大概率都在节点 2 的左右两侧路径是“节点 4 方向的最深叶子 - 节点 2 - 节点 5 方向的最深叶子”。这条路径的“拐点”是节点 2而不是根节点 1。如果只算根的左右深度因为根的右子树为空得到的结果大概是左子树深度加 0完全忽略了节点 2 下面左子树和右子树拼接出来的更长路径。这个反例清楚地说明了一件事树里任意一条路径一定存在一个“最高点”。沿着这条路径仰望整棵树总有一个节点路径从它的左子树方向上来再从右子树方向下去如果路径本身是直上直下的那最高点就是路径端点或某个祖先节点。所以与其只盯着根节点不如枚举所有节点作为候选“拐点”在每个节点处计算“左深度 右深度”然后取最大值。2.2 把所有节点都想成“拐点”问题就好办了一旦接受了“枚举拐点”的思想解法思路就清晰了我们需要对每个节点都拿到两样东西——左子树的最大深度、右子树的最大深度。任何一条最长路径都可以看作在某个拐点处把左右两条向下的路径拼接起来。这里其实就是树形 DP 的雏形。每个节点根据子树的信息算出“如果路径经过我最长能有多长”然后把这个候选值和全局最大值比较。接下来要解决的问题就只剩一个递归函数应该向上返回什么答案是返回该节点的最大深度也就是从当前节点出发能向下走到的最远的距离。因为父节点需要用这个值去计算“经过父节点的路径”而路径本身在当前节点这一层已经被记录过了。3. 后序遍历的递归设计一个返回值一个全局答案明确了“枚举拐点 后序遍历”的思路之后代码其实水到渠成。树的递归天然就是从下往上收集信息先处理左子树再处理右子树最后处理当前节点这正好是后序遍历。3.1 为什么必须先递归左右子树处理当前节点时我们需要知道左右子树各自的深度这个信息只能先通过递归拿到。所以代码结构必然是先调用dfs(node.left)和dfs(node.right)再计算当前节点能贡献的答案。这和你平时写前序遍历“先处理当前节点再进子树”不一样关键原因就是信息流向不同。前序遍历适合“从上往下传递信息”而后序遍历适合“从下往上汇总信息”。直径问题汇总的是左右子树的深度所以必须后序。3.2 JavaScript 实现与逐行拆解Leetcode 环境里二叉树节点的定义一般长这样function TreeNode(val, left, right) { this.val val undefined ? 0 : val; this.left left undefined ? null : left; this.right right undefined ? null : right; }完整解法如下function diameterOfBinaryTree(root) { let ans 0; function dfs(node) { // 空节点不贡献任何深度 if (!node) { return 0; } // 先拿到左右子树的深度 const left dfs(node.left); const right dfs(node.right); // 以当前节点为“拐点”的路径长度 ans Math.max(ans, left right); // 返回当前节点的最大深度给父节点用 return 1 Math.max(left, right); } dfs(root); return ans; }逐行拆解一下ans是全局变量用来收集所有“拐点”的候选答案。因为最长路径可能藏在任意子树内部必须在遍历过程中不断更新它。dfs(node)返回的是“从 node 出发向下最多能走多少个节点”。空节点返回 0叶子节点进入递归后左右都是 0于是return 1 Math.max(0, 0) 1。当前节点作为拐点时路径边数是left right。比如左子树返回 3右子树返回 4那经过当前节点的最长路径长度就是 7。最后return 1 Math.max(left, right)是给父节点用的深度。父节点拿到这个值后会把它当成自己左子树或右子树的深度继续向上汇总。这里最容易犯迷糊的一点是**ans并不是递归的返回值递归的返回值是深度。** 很多初学者把ans直接return给上层结果一变递归就乱了。你只需要记住向上返回的是“我能贡献多深的单侧深度”全局答案另算。3.3 两种代码风格全局变量 vs 返回对象有些面试官不太喜欢依赖外部变量或者会追问“如果不想用全局变量怎么办”。这个问题完全可以解决思路是让递归函数同时返回两个值子树的高度和子树内部的直径。function diameterOfBinaryTree(root) { function dfs(node) { if (!node) { return { height: 0, diameter: 0 }; } const left dfs(node.left); const right dfs(node.right); const height 1 Math.max(left.height, right.height); const diameter Math.max(left.diameter, right.diameter, left.height right.height); return { height, diameter }; } return dfs(root).diameter; }这种写法更“纯净”没有任何外部变量本质上是一个完整的多返回值树形 DP。两种方式的时间复杂度都是 O(N)我平时刷题用第一种因为代码短、直观面试被问到无副作用写法时再切到第二种。两种都会面试时才稳。4. 最容易翻车的三个细节空值语义、结果初始值、本地调试这道题代码虽然短但细节里藏着不少坑。我见过不止一个人“思路完全正确提交却报错”问题几乎都出在这几个地方。4.1 空节点返回 0 还是 -1各有什么代价这是一个非常经典的细节。有人会把递归函数定义成“返回从当前节点到叶子节点的边数”那么叶子节点应该返回 0空节点应该返回 -1。写成代码就是function dfs(node) { if (!node) return -1; const left dfs(node.left); const right dfs(node.right); ans Math.max(ans, left right 2); return 1 Math.max(left, right); }这种写法也能跑通但-1这个值出现得比较反直觉而且更新答案时要写成left right 2很容易算错。我推荐统一使用节点数口径空节点返回 0叶子返回 1更新答案直接用left right。这样代码更自然推导也更省心。记住一种口径就行不要每次写递归前都重新纠结。4.2 ans 初始值为什么是 0 而不是负数二叉树的直径最小可能是 0。什么情况下是 0空树和只有一个节点的树都是 0。空树里没有任何一条边单节点树里也只有这一个节点没有第二个节点可以连出路径。而left right这个公式在叶子节点处算出来是0 0 0所以ans初始化为 0 是安全的。如果题目改成求“最大路径和”这种节点值可能为负的题初始值就不能是 0 了得用负无穷。这是 124 题和 543 题的一个重要区别后面我会专门说到。4.3 本地怎么构造 TreeNode 把样例跑起来很多人喜欢在本地编辑器里调试 Leetcode 题但数组格式的输入并不等于 JavaScript 里的树对象。Leetcode 后台会自动把[1,2,3,4,5]转换成树结构可你在本地跑代码时得自己构造。最简单的办法是手写const root new TreeNode(1); root.left new TreeNode(2); root.right new TreeNode(3); root.left.left new TreeNode(4); root.left.right new TreeNode(5); console.log(diameterOfBinaryTree(root)); // 3如果你想验证更复杂的用例就一层层手动挂节点测试代码写在diameterOfBinaryTree外面。不建议为了本地测试去实现一个从数组建树的完整工具函数因为数组建树本身要考虑null占位、层序遍历逻辑写起来比这道题还长性价比不高。5. 边界用例实测链式树、单节点、复杂树全过一遍光看代码能跑通示例还不够我习惯把几种极端情况都测一遍这样心里才踏实。下面这几组用例基本覆盖了这道题的所有边界。5.1 链式树退化成链表结果是多少假如树退化成了单链1 - 2 - 3 - 4也就是每个节点只有左孩子。整棵树的最长路径就是从根走到最深的叶子或者从某个叶子走到另一个叶子其实单链上任意两个节点之间的路径只有一条最长的那条就是根到最远叶子边数是 3。用递归跑一遍节点 4 返回 1节点 3 拿到left 1, right 0更新ans Math.max(0, 1) 1然后返回 2节点 2 拿到left 2, right 0更新ans 2返回 3节点 1 拿到left 3, right 0更新ans 3最终答案 3。正确。这个用例说明即使左右子树只有一个方向有值left right依然能正确计算单侧路径不需要特殊处理。5.2 最大直径藏在左子树内部时的完整递归过程再看一个更“阴间”的用例根节点只有左孩子 2节点 2 有左右孩子 4 和 5节点 4 和节点 5 下又各挂一个叶子。也就是说根节点没有右子树但节点 2 的左右子树都很深。递归执行时节点 4 返回 2节点 5 返回 2。节点 2 处left 2, right 2更新ans 4返回1 2 3。根节点处left 3, right 0更新ans Math.max(4, 3) 4返回 4。最终答案 4。如果只看根节点左右深度得到 3那就错了。这个用例最能说明“为什么要遍历所有节点而不是只看根”。5.3 多种树形的结果对照表树形结构特点预期直径核心过程空树没有节点0不会进入递归单节点只有根0leftright0单链 1-2-3-4只有左链3在每层不断用单侧深度更新 ans根左右各一叶子1-2, 1-32根处 left1, right1最长路径在子树内部根只有左孩子左孩子左右很深取子树内部的左右拼接根处反而不是最大实测下来的规律很统一只要每个节点的left right都被纳入比较最终结果一定正确。这个做法本质上是动态规划里的“状态转移”只不过大多数时候不需要额外开数组用一个全局变量就够了。6. 一套思路延伸到四道高频题104、110、124、687543 的价值不只在题目本身。理解了“后序收集子树信息 更新全局答案 向上返回贡献值”这套框架你会发现好多所谓的高频难题其实都是同一个套路换了层皮。6.1 104 二叉树的最大深度只返回不更新104 最简单直接返回左右子树深度的最大值加 1function maxDepth(root) { if (!root) return 0; return 1 Math.max(maxDepth(root.left), maxDepth(root.right)); }它和 543 的关系在于543 的递归返回值部分就是在算最大深度。区别是 104 不需要横向拼接左右子树所以不需要全局ans。6.2 110 平衡二叉树用 -1 传递非法状态110 要求判断每个节点的左右子树高度差是否不超过 1。递归函数可以继续返回高度但一旦发现子树不平衡就返回 -1 作为哨兵。父节点收到 -1立刻能判断整棵树不平衡不需要额外定义全局变量。这和 543 的差异在于543 汇总的是“两个子树深度的和”110 关注的是“两个子树深度的差”。但信息收集方向完全一样都是从下往上。6.3 124 二叉树中的最大路径和把“高度”换成“贡献值”124 是最像 543 的进阶题。它要求路径上的节点值之和最大而且节点值可能是负数。套路依然是后序遍历但递归返回的不再是“深度”而是“从当前节点往下走能获得的最大贡献值”。关键细节是如果子树的贡献是负数就直接取 0不要带上它。更新答案时用leftGain rightGain node.val。因为节点值可正可负ans的初始值必须是-Infinity而不是 0否则全负数树会算错。这道题做完再回头看 543会理解得更透彻。6.4 687 最长同值路径再加一个“值相等”判断条件687 求的是“路径上所有节点值都相同”的最长路径。套路还是后序遍历但只有在子节点值和当前节点值相等时才能把子树的贡献算进来如果值不相等就相当于那条路径断开了贡献为 0。更新答案依然用类似left right的方式只是 left 和 right 已经被“值相等”过滤过。下面这张表总结一下这四道题与 543 的关系题目递归返回值更新答案方式特殊条件543 二叉树直径子树最大深度left right无104 最大深度子树最大深度不需要无110 平衡二叉树子树高度或 -1不需要高度差大于 1 返回 -1124 最大路径和向下最大贡献值leftGain rightGain node.val负贡献取 0ans 初始化为 -Infinity687 最长同值路径向下最长延伸长度left right仅当值相等时才累加刷题刷到后面你会发现二叉树的很多难题都长一个样递归函数做信息收集返回值尽量单一清晰需要横向比较时用全局变量。543 就是这个框架里最典型的入门例题。我自己后来再遇到树形 DP 的题都会先在草稿纸上画一棵小树标出每个节点递归应该返回什么、在哪个节点更新最终答案。画完这两栏代码基本就出来了剩下的只是把细节写对。这道 543 的 JavaScript 解法本质上就是“后序遍历 全局最大值”真正难的不是代码而是你愿不愿意相信最长路径的拐点可能藏在一棵不起眼的子树里。