递归函数返回值与全局变量：攻克LeetCode 543二叉树直径

从 day167 这个数字就能看出来我是在一个连续刷题的节奏里遇到 LeetCode-543 这道题的。那天本来想找个简单的题目松松手结果“二叉树的直径”这六个字把我按在原地快一个小时。递归我自认为练得不少二叉树的遍历、深度、翻转、最近公共祖先都刷过但到了直径这道题第一次写出来的代码看着很合理跑起来却全是错的。这篇文章就把我当时是怎么想的、为什么错、最后怎么改的过程完整拆开讲顺带把“递归”这个看起来入门、实际上天花板很高的概念也一起理清楚。如果你最近也在刷二叉树相关题目或者面试前想把手感练扎实这道题值得你多花点时间。1. 为什么987题里我偏偏对543印象最深1.1 这道题考察的是递归的两层职责大部分二叉树题目递归只需要你做好一件事返回一个值。比如最大深度递归函数返回“当前子树的最大深度”一路向上传答案自然就出来了。但 LeetCode-543 不一样它同时要求你做两件事递归函数的返回值负责向上传递“从当前节点往下走到最远叶子节点的深度信息”递归过程中还要通过一个外部变量通常叫diameter记录“以任意节点为转折点的最长路径长度”。这两件事混在同一段递归里一旦混淆代码就会出问题。我当时第一次写把返回值直接当成直径结果边界用例怎么跑都不对。后来才意识到return max(left, right) 1和diameter max(diameter, left right)是两件完全不同的事情一个给父节点用一个给最终答案用。这个拆分看起来简单但它其实是递归设计能力的分水岭。懂这个的人后面写 DP 遇到“返回值是状态、外部变量是最优值”的模式会非常顺畅不懂的人刷十道题还是靠背诵。1.2 通过率骗人看懂题解和手写出来是两回事LeetCode 上 543 的通过率不算低因为题解一搜一大把照着敲一遍很快能过。但如果你把窗口关掉拿出一张白纸从零开始写这个递归很多自称“刷过这道题”的人会卡住。我组里有个同事面某大厂的时候被问到这道题他告诉我“题解我背得滚瓜烂熟但面试官让我把递归过程画一遍我就露馅了。”为什么会露馅因为这道题的关键不在代码而在“为什么递归返回值是深度而不是直径的候选值”这个认知。理解了这个代码只是三行的事不理解背下来也是脆弱的。1.3 适合谁看 / 前置知识这篇文章适合两类人正在刷 LeetCode 的初学者你不需要已经精通递归只需要会对二叉树做基础的递归遍历看完本文能独立写出来。准备面试的进阶选手你可能会被问到底层原理比如“为什么直径不一定经过根节点”“递归的顺序为什么是后序”我会把这些也讲透。前置知识只需一个知道二叉树长什么样以及递归的基本语法。完全零基础的话建议先拿 LeetCode-104 最大深度热个身。2. 从暴力法到一次DFS先看解法演进的过程2.1 暴力的思路对每个节点都求一次两边最深我第一次拿到题目脑子里最先冒出来的思路是这样的直径是任意两个节点之间的最长路径路径肯定可以描述成“从某个节点出发向左下方走到底再向右下方走到底”。那最简单的方法就是遍历每一个节点对每个节点分别计算左子树的最大深度和右子树的最大深度两者相加就是以这个节点为最高转折点的路径长度然后取全局最大值。写成伪代码大概是for node in 树中所有节点: left_depth 计算节点左子树的最大深度 right_depth 计算节点右子树的最大深度 diameter max(diameter, left_depth right_depth)这个思路对不对逻辑上是对的。但它有一个很不划算的地方计算深度这个操作本身就是一次完整的递归遍历。假如树里有 N 个节点外层遍历每个节点是 O(N)内层每次求深度在最坏情况下又是 O(N)合起来就是 O(N²)。在 LeetCode 的测试数据规模下很多用例会直接超时。更关键的是这个暴力法里的“深度计算”和“直径更新”完全被拆开了重复劳动极其严重。一个节点的深度被它的所有祖先节点反复计算这种浪费在实际的递归调用里是完全没必要的。2.2 单边链反例为什么很多答案看着对其实错暴力法能过一部分用例但有一种特殊情况会暴露它的理解偏差当树严重偏向一侧时最长路径可能根本不经过根节点。举个例子构造这样一棵树1 \ 2 / \ 3 4 / \ / \ 5 6 7 8根节点 1 只有右子树。这时候以根节点为转折点的最长路径是从 1 一路下到最深的叶子比如 1-2-3-5长度是 3 条边。但是看一下节点 2它的左侧最长是 2-3-5右侧最长是 2-4-7左右加起来是从 5 到 7 经过 2、3、4 的路径长度是 4 条边。这条路径根本不经过根节点 1。所以如果你只计算“以根节点为中心”的左右深度之和答案就是 3但正确答案是 4。这就是为什么暴力法也必须在每个节点上都做同样的事情不能只看根节点。2.3 一次后序遍历的信息复用逻辑暴力法慢的根源是对同一个子树深度算了很多次。如果我们换一种思路先递归进入左右子树拿到它们的深度信息再回到当前节点做拼接就能保证每个节点只被访问一次。这个过程正好是后序遍历先算左子树再算右子树最后处理当前节点。递归函数把左右子树的深度一层层往上带每个节点拿到左右深度后既能更新全局直径又能继续向父节点返回自己的深度。一次 DFS 走完所有信息都有了时间复杂度降到 O(N)。这个“信息复用”的思路是所有自底向上递归的核心。你不需要额外记录每一棵子树的深度因为递归栈本身就是存储空间。3. 状态怎么设计返回“深度”更新“直径”3.1 递归函数只干一件事返回当前节点的最大深度这是整个题解最重要的一个设计决定。depth(node)这个函数定义非常单一传入一个节点返回“这个节点到它最远的叶子节点之间的距离”。这个距离用什么单位边数。也就是说一个叶子节点的深度是 0一个只有左叶子节点的父节点它的深度是 1。这样定义的好处是后面计算路径长度时会特别干净。计算方式就是经典的递归当前节点的深度 max(左子树深度, 右子树深度) 1空节点返回 0。这里没有任何歧义写出来也不会出错。3.2 全局变量如何被正确更新关键来了。在depth(node)里我们已经算出了left和right两个值。这两个值的含义是从左子树最深处走到当前节点再走到右子树最深处刚好就是穿过当前节点的最长路径。这条路径的边数等于left right。所以每个节点都会产生一个“候选答案”我们要做的就是拿它去更新全局的diameterdiameter max(diameter, left right)注意这里返回给父节点的值是max(left, right) 1而不是left right。前者是高度信息后者是路径信息。二者职责不同不能说谁比谁高级但用混了一定会错。在主函数里调用一次depth(root)递归过程中所有节点的候选答案都会考虑进去最后全局变量diameter就是题目要求的“直径”。3.3 代码实现Python / JavaPython 写法class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: self.diameter 0 def depth(node: Optional[TreeNode]) - int: if not node: return 0 left depth(node.left) right depth(node.right) self.diameter max(self.diameter, left right) return max(left, right) 1 depth(root) return self.diameterJava 写法class Solution { private int diameter 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return diameter; } private int depth(TreeNode node) { if (node null) return 0; int left depth(node.left); int right depth(node.right); diameter Math.max(diameter, left right); return Math.max(left, right) 1; } }这两份代码的核心逻辑完全一样。跑一个最简单的例子验证只有一个根节点左右都是空depth返回 0diameter保持 0答案是 0正确。三个节点[1,2,3]根节点拿到left1, right1diameter 2路径是 2-1-3 两条边正确。我在本地用 LeetCode 的示例跑过全部通过。但我更建议你自己手写一遍然后故意把diameter那行放到递归之前看看会发生什么。这一步能帮你深刻理解“先拿到子结果再更新父状态”的顺序。4. 三个高概率踩坑的认知误区4.1 误区一直径一定经过根节点上一节的单边链例子已经把这个误区打掉了。很多人的直觉是“树的最大直径应该以根为中心向左延伸一条向右延伸一条”。但树的结构是递归的最长路径可以完全发生在某一棵子树内部跟根节点一毛钱关系都没有。更进一步说即使路径经过了某个节点这个节点也不一定是根节点。它可以是任意一层的一个“转折点”。所以解法里才必须在每个节点上都做一次left right的更新而不是只在根节点算一次。我见过有人写了这样的代码def diameterOfBinaryTree(self, root): left self.depth(root.left) right self.depth(root.right) return left right单看这个函数它默认了路径必过根节点。这种写法遇到单边偏向、内部平衡的树时答案会偏小。4.2 误区二把“边数”和“节点数”混着用路径长度到底算边数还是算节点数题目原文说的是“边的数量”number of edges也就是两个节点之间的距离边数。一个三节点满二叉树直径是 2不是 3。但人的脑子很容易滑向“节点数”因为递归计算深度时有人习惯用节点数定义高度比如左右子树的最大节点数 1。如果你用节点数定义高度那么路径长度应该是左子树节点数 右子树节点数 1然后再减 1 才能转成边数。这一套换算非常容易出错。我的建议是把高度和路径全部统一为“边数”。叶子高度是 0空节点高度是 0递归返回max(left, right) 1无歧义路径就是left right直接当答案省掉所有加减 1 的魔法数字。4.3 误区三递归返回的左右值算完就扔还有一类错误代码长这样def diameterOfBinaryTree(self, root): def dfs(node): if not node: return 0 left dfs(node.left) right dfs(node.right) return max(left, right) 1 return dfs(root.left) dfs(root.right)这段代码的问题在于dfs只返回深度但深度不是直径。你最终答案用的是根节点左右子树的深度之和完全忽略了“直径可能在子树内部”这件事。相当于你把 4.1 的误区又踩了一遍只不过换了个写法。正确写法的关键就是那个全局变量。你必须在递归过程中每到一个节点都把left right拿去和全局最大值比一比而不是最后在根节点上做一次加法。这也是很多“明明逻辑没错但答案不对”的案例的根源。5. 写二叉树程序总报运行时错误的排查套路5.1 空指针和无限递归最常见的两类崩溃结合热搜词里“写二叉树程序时为什么总是报运行时错误”这几乎是每个刷二叉树的人都会撞上的问题。我总结下来排名前二的崩溃原因就是空指针和无限递归。空指针递归里最常见的场景就是先访问node.val或node.left再判断node是不是None。在 Python 里会报AttributeError在 Java 里是NullPointerException。排查方法很简单一行代码的事把空判断放在第一行if not node: return 0无限递归这个更隐蔽。常见诱因是递归参数写错比如该传node.left的地方传成了node或者左右子树调换了。另一种是有环结构树的题目基本不会但自己测试时可能构造出循环引用。表现就是程序永远跑不完Python 会直接RecursionErrorJava 则可能StackOverflowError。5.2 用一个三节点小树定位问题的完整过程拿一个最简单的测试用例比如root [1,2,3]。假设你的代码忘了判空然后你跑了这段def depth(node): return max(depth(node.left), depth(node.right)) 1控制台输出AttributeError: NoneType object has no attribute left报错信息指向node.left这一行而node已经成了None。这样的报错栈其实已经告诉了你问题某个递归调用传入了空节点但函数没有处理。修复之后再跑如果答案不是 2那问题可能出在更新时机。这时候我建议你手动模拟一遍调用过程从根节点开始按后序遍历的顺序先算左子树深度再算右子树深度回到根节点时左右都是 1更新diameter 2。纸面上能算清楚代码就不会写错。我实际调试时还有一个习惯递归函数里临时打印一份日志看看每次进入节点时的路径和返回的深度print(fnode{node.val}, left{left}, right{right}, diameter{self.diameter})打印完跑一个小用例哪里不对一目了然。定位到问题之后再把日志删掉。5.3 递归深度与栈溢出的现实问题二叉树退化成一个长链时递归深度就等于节点数。LeetCode 的测试数据通常不会让递归深到爆栈但如果你在本地用 Python 跑一个一万层的链式树RecursionError基本躲不掉。这时候有两个选择手动把 Python 递归上限调高sys.setrecursionlimit(20000)简单粗暴适合刷题环境。改写为迭代式 DFS用显式栈模拟后序遍历同时维护一个节点深度表。代码会明显变长但工程上更稳妥。面试时如果被问到“树特别深怎么办”能说出迭代方案绝对是加分项。不过日常刷题先掌握递归版本再考虑迭代版本不要本末倒置。6. 直径题的三个亲戚从543能顺带刷掉的题6.1 LeetCode 104最大深度是543的减配版最大深度那道题核心代码只有一行return max(depth(root.left), depth(root.right)) 1它只需要返回深度不需要全局变量不需要更新直径。如果你把 543 的depth函数写对了104 几乎是白送的。反过来说104 写得溜的人遇到 543 可能会懵因为后者多了一个“维护外部状态”的要求。两题对比着做能清晰看出递归“返回值”和“副作用”的区别。6.2 LeetCode 124把边数换成节点值后的变化124 是“二叉树中的最大路径和”结构上和 543 极其相似也是任意路径也可能不经过根节点也要用全局变量。区别只有两点路径的度量从“边数”变成了“节点值的累加和”。节点值可能是负数。负数这个变化很关键。在 543 里空节点返回 0深度永远是非负的所以left right天然合理。但在 124 里如果某条分支是负数你完全不应该把它纳入路径否则路径和反而变小。所以代码里需要一个“剪枝”操作left max(dfs(node.left), 0) right max(dfs(node.right), 0)把负数分支截断为 0表示“我不要这条分支”。这其实是把 543 的思路升级成了“带条件取舍”的版本。建议刷完 543 马上刷 124对比这两个max的用法理解会非常深刻。6.3 LeetCode 687同值路径给递归加约束687 是“最长同值路径”路径上所有节点的值都必须相同。表面看还是求直径但递归返回时多了一个限制只有当当前节点和左孩子的值相等时才能从左孩子那里继承深度同理右孩子也只有在值相等时才能被纳入计算。这个题让我想起把广度优先遍历换成条件判断时整体递归框架不变只是更新公式里的每一项都要先做“值相等”校验。你甚至可以先写 543 的模板然后逐行加上if node.left and node.left.val node.val这样的判断就能一路把 687 推出来。三个亲戚刷下来你会发现 543 不是一个孤立的题目而是一个“递归状态设计”的模板。返回值负责向上传递全局变量负责横向比较这个模式在二叉树、甚至更多图论问题里到处都在用。我个人刷到第167天的一个体会是递归题目最怕的不是不会写而是“以为自己会写了”。二叉树的直径这道题代码量不到十行但能卡住很多人恰恰说明它考的不是语法而是“递归里哪些信息该往上返、哪些信息该单独记录”的思维习惯。你在 LeetCode-543 上多花的一小时会在后面刷 124、687 以及更多递归题目时快速赚回来。如果你手边有编辑器我建议现在就打开不借助任何题解把depth函数写出来再想想那个全局变量该怎么放。写通这一题你会发现自己对递归的理解往上踏了一个台阶。