算法复健 Day12 - 二叉树 LC 226101104111最近在重刷算法题拿二叉树开刀算是比较舒服的复健路径。今天集中做掉四道 LeetCode 上的经典树题翻转二叉树LC 226、对称二叉树LC 101、二叉树的最大深度LC 104和最小深度LC 111。这四个题目正好覆盖了二叉树最核心的两种思维路径——递归遍历和层序迭代而且是同一个框架反复套用。这篇东西把每道题的思路、代码和踩坑点全部拆开讲清楚适合刷题新手、准备面试的选手以及像我一样隔了半年不看二叉树急需找回手感的人。题目本身不难但把四道题放在一起做你会发现在树的问题里“一棵树的递归模板”几乎能解决80%的题目剩下的20%靠的是对递归出口和返回值的精准理解。这四个题正好能从不同角度把递归和迭代两种写法都过一遍而且每道题都能用不同的遍历顺序解出非常值得一次性吃透。1. 二叉树问题的最优解题套路递归模板的搭建先别急着做题磨刀不误砍柴工。二叉树的题不管难易核心就两件事遍历和处理。遍历是指你按什么顺序访问每个节点处理是指你在访问到节点时对该节点做什么操作。绝大多数树的题本质上就是这两种操作的不同组合。1.1 为什么递归是二叉树问题的首选解法二叉树天然具有递归结构。一棵树的左子树和右子树本身也是二叉树这就意味着你在处理“当前节点”时可以用完全相同的逻辑去处理它的左右孩子。这种自相似性让递归成为最自然的解法——你不需要手动维护一个栈来模拟调用过程系统帮你把每一层调用的状态都压栈了。生活类比一下你让助手去整理一个档案柜每个抽屉里还套着小抽屉。递归的思路就是“每打开一个抽屉如果里面还有抽屉就执行同样的打开流程”你不用管整栋柜子有多少层只要把单层行为定义清楚系统会自动帮你处理嵌套。递归写法的好处体现在代码量上。一个翻转二叉树递归只需要几行如果用迭代写要手动维护栈代码量和出错概率都会明显上升。刷题阶段能用递归优先用递归不是因为迭代不好而是因为递归更贴近树结构的本质更容易正确实现。1.2 递归三步法终止条件、单层逻辑、返回值设计拿到一道树的递归题我习惯按三步去拆解第一步确定终止条件。也就是什么时候递归到头了绝大多数情况是当前节点为 null此时不需要处理直接返回 null 或者 0 这种“中性值”。这个中性值非常关键它决定了递归返回后上一层拿到的值是否正确。第二步确定单层递归逻辑。当节点不为空时你希望当前层做什么以翻转二叉树为例单层逻辑就是“交换左右孩子”。注意单层逻辑只管当前节点不要想着去处理整棵树递归会自动帮你完成剩下的部分。第三步确定递归返回值。你的递归函数返回什么东西是处理后的子树根节点还是子树的高度值还是布尔判断结果这一步决定了上一层怎么用这个返回值继续组合逻辑。返回值设计错了整棵递归树的回溯过程就全乱了。这三个步骤的逻辑顺序不能乱。很多人递归写错要么是终止条件写错比如该返回 0 的时候返回了 null要么是单层逻辑中多做了本不该当前层做的事比如在翻转二叉树里试图把孙子节点的位置也调了要么是返回值设计没有配合整体函数签名。1.3 递归与迭代的取舍两种写法各自的适用场景递归虽然优雅但也不是万能药。在树的深度非常大的情况下递归占用的是系统调用栈如果树的深度超过栈上限会直接爆栈Stack Overflow。而且递归的调式相对困难你很难在中间某一层停下来看状态。迭代写法则需要手动维护栈或者队列。栈适合深度优先遍历DFS队列适合广度优先遍历BFS。迭代的优势是可控性强不依赖系统栈而且在某些题里比如“求最小深度”迭代 BFS 反而是最优解因为 BFS 按层扩展找到第一个叶子节点时就是最小深度不需要遍历完整棵树。我的个人经验是做 LeetCode 题阶段树的深度一般不会大到爆栈递归完全够用。但如果你在工程里真的要处理一棵几千层深的树比如某些 XML 解析场景强制递归就会出事。所以两种写法都要会只是刷题时可以按优先级选递归。2. LC 226 翻转二叉树先序交换的递归实现与迭代备选这道题是 2024 年 LeetCode 的“百题斩”入门题同时也是“二叉树递归模板”最典型的一道。题面很简单给一棵二叉树的根节点翻转这棵树也就是把每个节点的左右子树都交换位置。2.1 递归解法先交换、再递归顺序不能乱翻转二叉树最自然的递归实现是这样的def invertTree(self, root): if not root: return None root.left, root.right root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root很多初学者会问为什么先交换再递归和先递归再交换效果不一样吗这里有个关键细节如果你先把当前节点的左右孩子交换了然后递归去处理左子树此时左子树已经是原来的右子树递归处理完返回的子树再赋回给 root.left最终的结果依然是翻转后的树。看起来先递归再交换也可以def invertTree(self, root): if not root: return None left self.invertTree(root.left) right self.invertTree(root.right) root.left right root.right left return root这两种写法一个叫“先序遍历式翻转”一个叫“后序遍历式翻转”都能得到正确答案。但是如果你写成“先递归处理左子树然后交换左右孩子再递归处理右子树”也就是中序遍历的顺序会出问题——因为你交换之后再去递归处理右子树时那个右子树其实已经是被处理过的左子树等于把同一个子树处理了两遍另一棵子树根本没被处理。这个坑我在初学时踩过代码跑了半天结果发现树只翻了一半排查很久才发现是遍历顺序错了。那到底选哪种我个人推荐第一种先交换再递归的版本因为逻辑更直观——你要翻转那就先交换再让递归去处理更小的子树。而且它和“通过交换达到翻转”的语义高度一致不容易在面试时把自己绕晕。2.2 迭代解法用栈手动模拟递归的过程如果你想练习迭代写法翻转二叉树同样可以做。核心思路是用一个栈按照栈的后进先出特性模拟递归调用每次从栈中弹出一个节点交换它的左右孩子然后把左右孩子重新压入栈中直到栈为空。def invertTree(self, root): if not root: return None stack [root] while stack: node stack.pop() node.left, node.right node.right, node.left if node.left: stack.append(node.left) if node.right: stack.append(node.right) return root这个迭代版本的“压栈顺序”其实无所谓先压左孩子还是先压右孩子都不影响最终结果因为每个节点都独立执行交换操作节点之间的处理顺序不相关。这跟“翻转操作满足交换律”一个道理你按不同顺序处理每个节点最终整棵树的翻转结果是一样的。2.3 本题的易错点与面试延展这道题面试中的常见坑有三个。第一空树处理如果传入的根节点是 None直接返回 None不要试图去访问 root.left否则会报空指针异常。第二链式赋值陷阱在 Python 里写root.left, root.right root.right, root.left是安全的因为 Python 会先计算右边的元组再赋值。但在某些语言里如果你写root.left root.right; root.right root.left结果就是两个子节点都变成了原来的右孩子左孩子直接丢失。第三返回值别漏递归函数最后一定要把处理完的 root 返回回去否则上一层递归拿到的就是 None整棵树就断了。面试时这道题常会被追问“如果树的节点数量很大递归会有什么风险”这其实是在考察你对系统调用栈的理解以及对迭代写法的掌握程度。能流畅给出两种解法并且说清楚各自适用场景基本就能拿下这题。3. LC 101 对称二叉树后序比较的结构判断对称二叉树这题比翻转稍微绕一点。它要求的不是翻转树而是判断一棵树是否“镜像对称”——也就是以根节点为轴左右子树互相对称。这题眼熟的原因在于它几乎是翻转二叉树的孪生兄弟翻转之后能和原树重合就说明对称。但在实际操作中判断对称比判断翻转更省事不需要真的改树的结构。3.1 对称的判断逻辑比较左右子树的“镜像位”对称的本质是什么一棵树对称意味着对于任意一层左子树的节点和右子树对应的镜像位置节点值相等。用根节点的左右子树来说左子树的左孩子要和右子树的右孩子相等左子树的右孩子要和右子树的左孩子相等。这个概念是这题的灵魂。很多第一次做这题的人会想“我能不能把根节点的左子树翻转一下再和右子树比较是否相等”理论上可以但实际操作起来要额外写一个翻转函数还会改变原树结构如果你没有深拷贝的话面试里完全没有必要。更优雅的方式是直接递归比较“镜像位”。3.2 递归判断一个函数比较两个节点的对称关系实现上写一个辅助函数isMirror(left, right)判断两棵子树是否互为镜像。终止条件有三种情况两个节点都为 null对称返回 True其中一个为 null 另一个不为 null不对称返回 False两个节点都不为 null先判断当前节点的值是否相等再递归判断left.left和right.right是否镜像同时判断left.right和right.left是否镜像。代码如下def isSymmetric(self, root): if not root: return True return self.isMirror(root.left, root.right) def isMirror(self, left, right): if not left and not right: return True if not left or not right: return False return (left.val right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left))这个递归的终止条件设计是有讲究的。not left and not right判断要写在not left or not right之前因为逻辑顺序是“两者都空 → 对称有一方为空 → 不对称都不为空 → 继续比”。如果顺序反了not left and not right会被后面的条件覆盖空节点对会在“有一方为空”时返回 False结果就错了。3.3 迭代方式队列成对比较的写法与注意事项对称二叉树的迭代写法也很有意思。思路是用一个队列每次成对取出两个节点进行比较。初始时把 root.left 和 root.right 放入队列然后每次弹出两个节点如果两个都为 null 则继续如果只有一个为 null 则返回 False值不同也返回 False然后把“左的左”和“右的右”成对入队把“左的右”和“右的左”成对入队。def isSymmetric(self, root): if not root: return True queue [root.left, root.right] while queue: left queue.pop(0) right queue.pop(0) if not left and not right: continue if not left or not right: return False if left.val ! right.val: return False queue.append(left.left) queue.append(right.right) queue.append(left.right) queue.append(right.left) return True用 Python 的queue.pop(0)效率不高这是列表实现队列的天然短板。实战中建议用collections.deque的popleft()复杂度是 O(1)。这是个性能优化细节面试时如果你能主动说出来会是个加分项。这道题如果和翻转二叉树连着做很容易产生一个有趣的想法对称二叉树能不能转换成“翻转之后等于原树”来判断能但就像前面说的不需要真的改树。你可以在概念上理解这两个题是相通的但在代码实现上用镜像递归更简洁也更安全。4. LC 104 最大深度后序遍历统计层数的标准解法最大深度这题几乎是所有树相关的算法题的基础题。什么叫深度根节点到最远叶子节点的最长路径上的节点数。这题虽然简单但它的递归返回值设计非常有代表性掌握了它很多类似题比如平衡二叉树、直径问题都能迎刃而解。4.1 递归求深度为什么用后序遍历最大深度的递归解法就是经典的“后序遍历”应用——先获取左子树深度再获取右子树深度然后取两者最大值加一作为当前节点的深度。为什么要后序因为当前节点的深度依赖于左右子树的深度你得先把子树的结果算出来才能往上汇总。def maxDepth(self, root): if not root: return 0 left_depth self.maxDepth(root.left) right_depth self.maxDepth(root.right) return max(left_depth, right_depth) 1这个代码短小精悍但信息量很大。首先终止条件是空节点返回 0这符合“空树深度为 0”的定义。其次中间两行分别递归计算左右子树的深度它们之间互不干扰。最后取最大值加一加的这个 1 代表当前节点本身也要算进深度里。验证一下一棵只有一个根节点的树左右子树都是空递归返回 0 和 0最大值是 0再加 1 得到 1说明深度为 1。一棵有根节点和一个左孩子的树左子树是一个叶子节点它的深度是 1右子树深度 0取最大值 1 再加 1 得到 2正确。这个验证过程建议你自己在纸上画一下能加深对递归回溯过程的理解。4.2 迭代写法层序遍历法每进入一层计数加 1如果你想用迭代的方式求最大深度最直观的做法就是层序遍历BFS。每一层节点处理完深度加 1直到队列为空。因为最大深度本质上就是“这棵树一共有多少层”。from collections import deque def maxDepth(self, root): if not root: return 0 queue deque([root]) depth 0 while queue: size len(queue) for _ in range(size): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth 1 return depth这里有个细节值得注意每轮循环开始时用size len(queue)记录当前层的节点数然后只处理这 size 个节点这样能保证每轮处理完整的一层。如果不这样做直接用while queue加popleft你无法区分哪些节点属于同一层计数就会错。这个 trick 在 BFS 相关题目里广泛使用比如“二叉树的右视图”“层平均值”等题都要靠这个技巧把逐层信息提取出来。4.3 递归深度的隐含考点回溯与归并的时机熟悉回溯算法的同学能从这个简单题里看到一个重要的概念——递归函数返回值的设计直接影响了回溯时的数据处理方式。在最大深度这题中递归深度的计算采用的是“归并式”回溯每层递归把两个子递归的结果合并后返回。这跟“回溯法”比如排列组合问题有点区别后者在递归前修改状态在递归后撤销修改。“回溯”这个词在树的题目里常被提及但很多时候大家只记住了名字没搞懂它真正的执行时机。在最大深度这个问题里函数调用self.maxDepth(root.left)时会一直扎到最底层然后逐层返回每一层拿到两个子深度后做一个 max 运算再 1然后返回给更上层。这个从底层向上传递结果的过程在很多复杂树题比如判断平衡二叉树中是核心逻辑建议你现在就把这个“归并回到上一层”的画面在脑子里建立起来。5. LC 111 最小深度看似差不多实际暗藏玄机题目做多了容易把“最大深度”和“最小深度”当成同一个思路的两种问法。但注意了最小深度这里有个大坑稍不注意就会做错。题目定义最小深度是根节点到最近叶子节点的最短路径上的节点数。5.1 最小深度不是“最大深度的镜像版”很多人拿到最小深度的第一反应是“把 max 改成 min 不就行了”# 错误示范 def minDepth(self, root): if not root: return 0 left self.minDepth(root.left) right self.minDepth(root.right) return min(left, right) 1这个代码单独看好像没问题但它有一个致命缺陷对于一棵只有左子树、没有右子树的树右子树返回 0min 取 0那么结果就是 1。可是这棵树的最小深度真的是 1 吗不是。因为根节点不是叶子节点它还有左孩子真正的最近叶子节点在左子树上最小深度应该等于左子树的深度加 1而不是 1。问题出在空节点的含义上。空节点不能简单当作“深度为 0”因为在最小深度的定义里空节点不构成任何连向叶子节点的路径。空节点更像是一个“无效值”你需要跳过它只考虑非空子树的情况。5.2 递归正确写法分类讨论左右子树的存在性正确的写法需要区分三种情况左右子树都为空当前节点是叶子节点返回 1左右子树有一个为空最小深度取决于非空的那一侧返回非空子树的深度加 1左右子树都不为空取两者较小值加 1。def minDepth(self, root): if not root: return 0 if not root.left and not root.right: return 1 if not root.left: return self.minDepth(root.right) 1 if not root.right: return self.minDepth(root.left) 1 return min(self.minDepth(root.left), self.minDepth(root.right)) 1这个分类讨论比 max 版本多了几个分支是因为空节点的“语义”变了。在 max 中空节点是合法的 0你可以放心取 max但在 min 中空节点是一个陷阱你绝不能把 0 作为最小值参与比较否则任何只有单边子树的树都会错误地返回 1。仔细体会一下这题的价值——它提醒你在算法题里“定义”决定“实现”。你对“最小深度”的理解稍有偏差代码的结果就会出现系统性错误。面试官出这题很大概率就是在看你会不会忽略单边子树这种情况。5.3 迭代 BFS 解法遇到第一个叶子节点就返回最小深度用 BFS 迭代写其实比递归更直接。因为 BFS 是逐层扩展的你第一次遇到的叶子节点一定处于最小的层数此时返回当前深度计数即可。这个思路不需要像递归那样分类讨论逻辑非常干净。from collections import deque def minDepth(self, root): if not root: return 0 queue deque([(root, 1)]) while queue: node, depth queue.popleft() if not node.left and not node.right: return depth if node.left: queue.append((node.left, depth 1)) if node.right: queue.append((node.right, depth 1))这个解法用(root, 1)的形式把节点和深度打包存入队列每往下一层 depth 加一。当你访问到某个节点发现它没有左右孩子这个节点就是叶子节点直接返回当前 depth 就是最小深度。BFS 天然保证找到的第一个叶子节点一定在最小的层数这是深度优先遍历做不到的——DFS 可能会先走一条很深的路径浪费大量时间。如果你“比较较真”可能会问不用元组能不能只存节点用一个额外的 depth 变量可以但要注意由于 BFS 是逐层处理的每轮循环的节点深度相同所以也可以像前面“最大深度层序遍历”那样在每轮循环结束后 depth 1然后在进入下一轮循环之前检测是否存在叶子节点。元组法更直观也更省事扩展到其他需要携带额外状态的 BFS 题目时也更方便。6. 四道题合练通用模板与刷题复盘把四道题放在一起复盘你会发现它们的代码高度相似区别只在于返回值和终止条件的设计。这就是“刷树题组”的价值所在——帮你识别模式而不是孤立地记题目。6.1 四题解法对比表递归返回值设计与遍历顺序差异题目递归模板核心遍历顺序返回值类型关键难点LC 226 翻转二叉树交换 双递归先序 / 后序TreeNode注意不能中序LC 101 对称二叉树成对比较镜像位后序成对递归bool递归辅助函数两个参数LC 104 最大深度max(左右深度) 1后序int空节点返回 0LC 111 最小深度分类讨论单边子树后序 / 层序int空节点不能当 0 比较这四类返回值基本覆盖了二叉树递归题的主要返回类型返回修改后的树、返回布尔判断、返回数值统计。面试时拿到一道树题先判断返回类型再确定遍历顺序然后写终止条件这个流程可以应对 90% 的树题。6.2 关于递归写法的一些实战心得递归的代码虽短但真正想清楚每一步的执行过程还是需要花时间的。我最开始练习递归时有个笨办法在纸上把递归调用树画出来每次递归画一个圈回溯时画一条向上的箭头同时把返回值写在箭头旁边。画了好几棵树之后“递归就是函数调用自己、每一层有独立的状态、返回值逐层汇总”这个概念才算真正内化。另外一个有用的技巧是写递归时假想自己只能看到当前节点。不要去想“我这层的操作会怎么影响整棵树”专注于当前节点应该做什么操作、应该接收什么返回值、应该往上层返回什么。把这三个问题想清楚代码基本不会写错。很多人递归写不好就是因为脑子里总想着整棵树越想越混乱。调试递归还有一个现实的问题Python 默认的递归深度限制是 1000 层。在 LeetCode 上很多题目的树深不会超过这个限制但如果你自己造了一个极端测试用例比如一条 2000 层的链式树直接会抛RecursionError。遇到这种情况不是你的算法错了而是递归深度的工程限制。了解这个限制对于写生产代码很重要但在刷题阶段多数情况不用过度担心。6.3 二叉树题目的延伸方向正则化练习路径做完这四个题你可以继续沿着二叉树主线往两个方向扩展。第一个方向是“深度类问题”的延伸比如判断平衡二叉树LC 110本质上就是在求深度后加一个平衡性判断比如求二叉树直径LC 543需要在求深度的同时统计“经过某节点的最大路径长度”。这些题都复用最大深度的递归框架只是返回值增加了额外信息。第二个方向是“对称 / 翻转”类问题的延伸比如判断两棵树是否相同LC 100把“镜像比较”改成“直接比较”就行比如构造镜像树或二叉树的序列化与反序列化。翻转到对称这组题练完后你对“递归参数是两个节点”的写法会非常熟悉这种双参数递归在更多树题中比如最近公共祖先 LC 236有变体应用。做题的时候我习惯用一个简单的路径去强化记忆先从递归模板入手每道题都写出递归解法然后把其中一两题用迭代写法实现一遍体会两者在空间复杂度和代码风格上的差别。这样四道题做完你基本上把二叉树最基础也是最核心的套路全部过了一遍后续刷更复杂的树题会顺手很多。7. 常见问题排查单侧子树、空指针与返回值丢失这一节集中讲我做这四道题时实际踩过的坑以及读者私信问过我的高频问题。这些问题看着小但每一个都能让代码报错或者结果错误。7.1 单侧子树为什么是最大深度的陷阱最大深度的代码看起来简单但如果你稍微改一下把终止条件写成“没有左右孩子时返回 1”然后左右子树递归时不做空处理就会出问题。比如一棵只有左子树的链式树递归会沿着左子树一路往下走右子树每层都是 None你必须在递归到来时正确返回 0否则函数会在 None 上调用.minDepth()直接抛 AttributeError。这个问题的根源在于递归函数必须在进入递归体的第一行就处理空节点。很多人习惯先判断 root 是否为空再递归这是对的但要确保所有递归调用都经过了空节点检查。我的习惯是在一道树题的递归函数开头永远写一行if not root: return ...作为兜底这样后续代码就能放心使用 root 的属性而不用担心空指针。最大深度本身也有一个隐含的坑如果你把空树返回 0单节点树返回 1那么递归式max(left, right) 1就是安全的。如果你试图省掉空检查直接在 root 上调用maxDepth(root.left)那 root.left 为 None 时None 会传入函数函数的if not root就会兜住其实空检查本身已经写在函数开头了。这样反而没问题。真正错误的是在调用前对 None 做属性访问那才是空指针。7.2 递归返回值丢失的典型场景与定位技巧递归函数里最隐蔽的错误就是返回值丢失。以翻转二叉树为例有些人写完交换逻辑后忘记在函数末尾返回 root那么最终函数返回的就是 None。由于翻转操作是在原树上做的从 root 出发访问实际树时树已经被修改了看起来结果可能是对的。但是在对称二叉树的判断里如果你在递归比较时某个分支忘记把结果返回得到的就是 None而这会被外层当成 False导致对称判断失灵。这类问题的定位方式我总结了一个小技巧在递归函数末尾打一个临时打印输出当前节点的值和返回值。运行一个很小的测试用例对比打印结果和你手工推演的结果差异点在哪个节点哪里就出问题了。排查树题的错误用“小而精”的测试用例比大而全的用例更容易定位。7.3 层序遍历的队列首元素弹出性能Python 的列表pop(0)是一个 O(n) 操作因为弹出头部元素后剩余元素需要整体往前挪一位。在层序遍历里如果你用pop(0)处理一棵节点数上万的树性能会明显变差。正确做法是用collections.deque它的popleft()是 O(1)。这虽然是个小点但在我写 BFS 版本的层序遍历时被面试官专门指出过后来我就养成了一个习惯凡是要用队列的地方一律用 deque不再用列表模拟队列。另一个队列相关的小建议是在迭代 BFS 里如果要记录每个节点对应的层数或路径用元组入队最直观。但在内存敏感的代码中元组的开销要略高于单独维护一个数组这时候可以根据场景选择维护一个“层数数组”并与节点索引对应或者使用两个队列分隔节点和深度。在 LeetCode 题目的数据规模下元组方案完全够用可读性也更好。7.4 测试用例设计从一棵树到多棵树刷这四道题时我建议你用几个固定测试用例来验证代码一棵空树验证空节点返回逻辑一棵只有根节点的树验证叶子节点的返回逻辑一棵普通的三层满二叉树验证一般情况的递归正确性一棵只有左子树的链式树或者只有右子树专门测最小深度和单边子树问题一棵左右子树深度不同的树验证最大深度的 max 逻辑。这种“边界 常规 极端”的测试思路不仅适用于树题适用于任何算法题。LeetCode 虽然自带测试用例但自己主动构造边界条件能更早发现代码的脆弱点。8. 四题之外的延伸思考从模板到举一反三这四道题练完你可能会觉得“树的题好像也没那么难”。这个感觉是对的但要注意它是因为你把基础模式吃透了。四题之外的进阶题比如“二叉树最近公共祖先”“二叉树的序列化与反序列化”“二叉树的最大路径和”都是在基础模板上添加状态处理或返回值语义拓展。8.1 双参数递归从对称二叉树到最近公共祖先对称二叉树用到的是isMirror(left, right)这种双参数递归。这个模式在后续的树题中非常常见。比如最近公共祖先LCA问题你需要在一个递归函数里同时处理两个目标节点的查找返回值可以是“找到的节点”或者“空”。从“单参数遍历”到“双参数比较”的跃迁本质上是递归的输入状态从“一棵子树”扩展到了“两个子树的对应位置”理解了对称二叉树的isMirrorLCA 的分支逻辑就不难接受。8.2 深度类问题的统一框架从最大深度到直径问题最大深度max(left, right) 1这个框架可以无缝对接到二叉树直径问题。直径的定义是“任意两节点间最长路径的边数”它等价于经过某个根节点的左子树深度加右子树深度。你在递归求深度的过程中顺便用一个全局变量记录left right的最大值最后返回的全局变量就是直径。这类“递归计算主返回值 全局变量辅助记录额外信息”的模式是很多高级树题的通用解法。建议你在做完最大深度后立刻尝试一道直径题能加深对这个模式的理解。8.3 思考题如果再加一个“最大直径”和“平衡判断”把题目延伸一下LC 110 平衡二叉树本质上就是“左右子树深度差不超过 1”这可以复用最大深度的递归在返回值之外用一个全局标记记录是否平衡。LC 543 二叉树直径需要返回的不仅是节点深度还要考虑左右子树深度之和的最大值。这些题本质上都在问同一个问题——“你能否在递归过程中额外携带并维护状态”。这些状态可以是最大值、最小值、布尔值、或者是另一个节点的引用。掌握了这个“额外状态携带”的思路你在树这个专题上的能力会比只刷几道基础题提升一个量级。我在实际刷题中有一个体会树题的提升速度不太靠大量刷题靠的是反复咀嚼少数题的递归结构和状态设计。今天这四道题恰好覆盖了“修改结构”、“比较结构”、“统计深度”三种返回语义你把它们的异同吃透比囫囵吞枣做出二十道题更有收获。
二叉树算法复健：翻转、对称、最大/最小深度一次吃透
算法复健 Day12 - 二叉树 LC 226101104111最近在重刷算法题拿二叉树开刀算是比较舒服的复健路径。今天集中做掉四道 LeetCode 上的经典树题翻转二叉树LC 226、对称二叉树LC 101、二叉树的最大深度LC 104和最小深度LC 111。这四个题目正好覆盖了二叉树最核心的两种思维路径——递归遍历和层序迭代而且是同一个框架反复套用。这篇东西把每道题的思路、代码和踩坑点全部拆开讲清楚适合刷题新手、准备面试的选手以及像我一样隔了半年不看二叉树急需找回手感的人。题目本身不难但把四道题放在一起做你会发现在树的问题里“一棵树的递归模板”几乎能解决80%的题目剩下的20%靠的是对递归出口和返回值的精准理解。这四个题正好能从不同角度把递归和迭代两种写法都过一遍而且每道题都能用不同的遍历顺序解出非常值得一次性吃透。1. 二叉树问题的最优解题套路递归模板的搭建先别急着做题磨刀不误砍柴工。二叉树的题不管难易核心就两件事遍历和处理。遍历是指你按什么顺序访问每个节点处理是指你在访问到节点时对该节点做什么操作。绝大多数树的题本质上就是这两种操作的不同组合。1.1 为什么递归是二叉树问题的首选解法二叉树天然具有递归结构。一棵树的左子树和右子树本身也是二叉树这就意味着你在处理“当前节点”时可以用完全相同的逻辑去处理它的左右孩子。这种自相似性让递归成为最自然的解法——你不需要手动维护一个栈来模拟调用过程系统帮你把每一层调用的状态都压栈了。生活类比一下你让助手去整理一个档案柜每个抽屉里还套着小抽屉。递归的思路就是“每打开一个抽屉如果里面还有抽屉就执行同样的打开流程”你不用管整栋柜子有多少层只要把单层行为定义清楚系统会自动帮你处理嵌套。递归写法的好处体现在代码量上。一个翻转二叉树递归只需要几行如果用迭代写要手动维护栈代码量和出错概率都会明显上升。刷题阶段能用递归优先用递归不是因为迭代不好而是因为递归更贴近树结构的本质更容易正确实现。1.2 递归三步法终止条件、单层逻辑、返回值设计拿到一道树的递归题我习惯按三步去拆解第一步确定终止条件。也就是什么时候递归到头了绝大多数情况是当前节点为 null此时不需要处理直接返回 null 或者 0 这种“中性值”。这个中性值非常关键它决定了递归返回后上一层拿到的值是否正确。第二步确定单层递归逻辑。当节点不为空时你希望当前层做什么以翻转二叉树为例单层逻辑就是“交换左右孩子”。注意单层逻辑只管当前节点不要想着去处理整棵树递归会自动帮你完成剩下的部分。第三步确定递归返回值。你的递归函数返回什么东西是处理后的子树根节点还是子树的高度值还是布尔判断结果这一步决定了上一层怎么用这个返回值继续组合逻辑。返回值设计错了整棵递归树的回溯过程就全乱了。这三个步骤的逻辑顺序不能乱。很多人递归写错要么是终止条件写错比如该返回 0 的时候返回了 null要么是单层逻辑中多做了本不该当前层做的事比如在翻转二叉树里试图把孙子节点的位置也调了要么是返回值设计没有配合整体函数签名。1.3 递归与迭代的取舍两种写法各自的适用场景递归虽然优雅但也不是万能药。在树的深度非常大的情况下递归占用的是系统调用栈如果树的深度超过栈上限会直接爆栈Stack Overflow。而且递归的调式相对困难你很难在中间某一层停下来看状态。迭代写法则需要手动维护栈或者队列。栈适合深度优先遍历DFS队列适合广度优先遍历BFS。迭代的优势是可控性强不依赖系统栈而且在某些题里比如“求最小深度”迭代 BFS 反而是最优解因为 BFS 按层扩展找到第一个叶子节点时就是最小深度不需要遍历完整棵树。我的个人经验是做 LeetCode 题阶段树的深度一般不会大到爆栈递归完全够用。但如果你在工程里真的要处理一棵几千层深的树比如某些 XML 解析场景强制递归就会出事。所以两种写法都要会只是刷题时可以按优先级选递归。2. LC 226 翻转二叉树先序交换的递归实现与迭代备选这道题是 2024 年 LeetCode 的“百题斩”入门题同时也是“二叉树递归模板”最典型的一道。题面很简单给一棵二叉树的根节点翻转这棵树也就是把每个节点的左右子树都交换位置。2.1 递归解法先交换、再递归顺序不能乱翻转二叉树最自然的递归实现是这样的def invertTree(self, root): if not root: return None root.left, root.right root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root很多初学者会问为什么先交换再递归和先递归再交换效果不一样吗这里有个关键细节如果你先把当前节点的左右孩子交换了然后递归去处理左子树此时左子树已经是原来的右子树递归处理完返回的子树再赋回给 root.left最终的结果依然是翻转后的树。看起来先递归再交换也可以def invertTree(self, root): if not root: return None left self.invertTree(root.left) right self.invertTree(root.right) root.left right root.right left return root这两种写法一个叫“先序遍历式翻转”一个叫“后序遍历式翻转”都能得到正确答案。但是如果你写成“先递归处理左子树然后交换左右孩子再递归处理右子树”也就是中序遍历的顺序会出问题——因为你交换之后再去递归处理右子树时那个右子树其实已经是被处理过的左子树等于把同一个子树处理了两遍另一棵子树根本没被处理。这个坑我在初学时踩过代码跑了半天结果发现树只翻了一半排查很久才发现是遍历顺序错了。那到底选哪种我个人推荐第一种先交换再递归的版本因为逻辑更直观——你要翻转那就先交换再让递归去处理更小的子树。而且它和“通过交换达到翻转”的语义高度一致不容易在面试时把自己绕晕。2.2 迭代解法用栈手动模拟递归的过程如果你想练习迭代写法翻转二叉树同样可以做。核心思路是用一个栈按照栈的后进先出特性模拟递归调用每次从栈中弹出一个节点交换它的左右孩子然后把左右孩子重新压入栈中直到栈为空。def invertTree(self, root): if not root: return None stack [root] while stack: node stack.pop() node.left, node.right node.right, node.left if node.left: stack.append(node.left) if node.right: stack.append(node.right) return root这个迭代版本的“压栈顺序”其实无所谓先压左孩子还是先压右孩子都不影响最终结果因为每个节点都独立执行交换操作节点之间的处理顺序不相关。这跟“翻转操作满足交换律”一个道理你按不同顺序处理每个节点最终整棵树的翻转结果是一样的。2.3 本题的易错点与面试延展这道题面试中的常见坑有三个。第一空树处理如果传入的根节点是 None直接返回 None不要试图去访问 root.left否则会报空指针异常。第二链式赋值陷阱在 Python 里写root.left, root.right root.right, root.left是安全的因为 Python 会先计算右边的元组再赋值。但在某些语言里如果你写root.left root.right; root.right root.left结果就是两个子节点都变成了原来的右孩子左孩子直接丢失。第三返回值别漏递归函数最后一定要把处理完的 root 返回回去否则上一层递归拿到的就是 None整棵树就断了。面试时这道题常会被追问“如果树的节点数量很大递归会有什么风险”这其实是在考察你对系统调用栈的理解以及对迭代写法的掌握程度。能流畅给出两种解法并且说清楚各自适用场景基本就能拿下这题。3. LC 101 对称二叉树后序比较的结构判断对称二叉树这题比翻转稍微绕一点。它要求的不是翻转树而是判断一棵树是否“镜像对称”——也就是以根节点为轴左右子树互相对称。这题眼熟的原因在于它几乎是翻转二叉树的孪生兄弟翻转之后能和原树重合就说明对称。但在实际操作中判断对称比判断翻转更省事不需要真的改树的结构。3.1 对称的判断逻辑比较左右子树的“镜像位”对称的本质是什么一棵树对称意味着对于任意一层左子树的节点和右子树对应的镜像位置节点值相等。用根节点的左右子树来说左子树的左孩子要和右子树的右孩子相等左子树的右孩子要和右子树的左孩子相等。这个概念是这题的灵魂。很多第一次做这题的人会想“我能不能把根节点的左子树翻转一下再和右子树比较是否相等”理论上可以但实际操作起来要额外写一个翻转函数还会改变原树结构如果你没有深拷贝的话面试里完全没有必要。更优雅的方式是直接递归比较“镜像位”。3.2 递归判断一个函数比较两个节点的对称关系实现上写一个辅助函数isMirror(left, right)判断两棵子树是否互为镜像。终止条件有三种情况两个节点都为 null对称返回 True其中一个为 null 另一个不为 null不对称返回 False两个节点都不为 null先判断当前节点的值是否相等再递归判断left.left和right.right是否镜像同时判断left.right和right.left是否镜像。代码如下def isSymmetric(self, root): if not root: return True return self.isMirror(root.left, root.right) def isMirror(self, left, right): if not left and not right: return True if not left or not right: return False return (left.val right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left))这个递归的终止条件设计是有讲究的。not left and not right判断要写在not left or not right之前因为逻辑顺序是“两者都空 → 对称有一方为空 → 不对称都不为空 → 继续比”。如果顺序反了not left and not right会被后面的条件覆盖空节点对会在“有一方为空”时返回 False结果就错了。3.3 迭代方式队列成对比较的写法与注意事项对称二叉树的迭代写法也很有意思。思路是用一个队列每次成对取出两个节点进行比较。初始时把 root.left 和 root.right 放入队列然后每次弹出两个节点如果两个都为 null 则继续如果只有一个为 null 则返回 False值不同也返回 False然后把“左的左”和“右的右”成对入队把“左的右”和“右的左”成对入队。def isSymmetric(self, root): if not root: return True queue [root.left, root.right] while queue: left queue.pop(0) right queue.pop(0) if not left and not right: continue if not left or not right: return False if left.val ! right.val: return False queue.append(left.left) queue.append(right.right) queue.append(left.right) queue.append(right.left) return True用 Python 的queue.pop(0)效率不高这是列表实现队列的天然短板。实战中建议用collections.deque的popleft()复杂度是 O(1)。这是个性能优化细节面试时如果你能主动说出来会是个加分项。这道题如果和翻转二叉树连着做很容易产生一个有趣的想法对称二叉树能不能转换成“翻转之后等于原树”来判断能但就像前面说的不需要真的改树。你可以在概念上理解这两个题是相通的但在代码实现上用镜像递归更简洁也更安全。4. LC 104 最大深度后序遍历统计层数的标准解法最大深度这题几乎是所有树相关的算法题的基础题。什么叫深度根节点到最远叶子节点的最长路径上的节点数。这题虽然简单但它的递归返回值设计非常有代表性掌握了它很多类似题比如平衡二叉树、直径问题都能迎刃而解。4.1 递归求深度为什么用后序遍历最大深度的递归解法就是经典的“后序遍历”应用——先获取左子树深度再获取右子树深度然后取两者最大值加一作为当前节点的深度。为什么要后序因为当前节点的深度依赖于左右子树的深度你得先把子树的结果算出来才能往上汇总。def maxDepth(self, root): if not root: return 0 left_depth self.maxDepth(root.left) right_depth self.maxDepth(root.right) return max(left_depth, right_depth) 1这个代码短小精悍但信息量很大。首先终止条件是空节点返回 0这符合“空树深度为 0”的定义。其次中间两行分别递归计算左右子树的深度它们之间互不干扰。最后取最大值加一加的这个 1 代表当前节点本身也要算进深度里。验证一下一棵只有一个根节点的树左右子树都是空递归返回 0 和 0最大值是 0再加 1 得到 1说明深度为 1。一棵有根节点和一个左孩子的树左子树是一个叶子节点它的深度是 1右子树深度 0取最大值 1 再加 1 得到 2正确。这个验证过程建议你自己在纸上画一下能加深对递归回溯过程的理解。4.2 迭代写法层序遍历法每进入一层计数加 1如果你想用迭代的方式求最大深度最直观的做法就是层序遍历BFS。每一层节点处理完深度加 1直到队列为空。因为最大深度本质上就是“这棵树一共有多少层”。from collections import deque def maxDepth(self, root): if not root: return 0 queue deque([root]) depth 0 while queue: size len(queue) for _ in range(size): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth 1 return depth这里有个细节值得注意每轮循环开始时用size len(queue)记录当前层的节点数然后只处理这 size 个节点这样能保证每轮处理完整的一层。如果不这样做直接用while queue加popleft你无法区分哪些节点属于同一层计数就会错。这个 trick 在 BFS 相关题目里广泛使用比如“二叉树的右视图”“层平均值”等题都要靠这个技巧把逐层信息提取出来。4.3 递归深度的隐含考点回溯与归并的时机熟悉回溯算法的同学能从这个简单题里看到一个重要的概念——递归函数返回值的设计直接影响了回溯时的数据处理方式。在最大深度这题中递归深度的计算采用的是“归并式”回溯每层递归把两个子递归的结果合并后返回。这跟“回溯法”比如排列组合问题有点区别后者在递归前修改状态在递归后撤销修改。“回溯”这个词在树的题目里常被提及但很多时候大家只记住了名字没搞懂它真正的执行时机。在最大深度这个问题里函数调用self.maxDepth(root.left)时会一直扎到最底层然后逐层返回每一层拿到两个子深度后做一个 max 运算再 1然后返回给更上层。这个从底层向上传递结果的过程在很多复杂树题比如判断平衡二叉树中是核心逻辑建议你现在就把这个“归并回到上一层”的画面在脑子里建立起来。5. LC 111 最小深度看似差不多实际暗藏玄机题目做多了容易把“最大深度”和“最小深度”当成同一个思路的两种问法。但注意了最小深度这里有个大坑稍不注意就会做错。题目定义最小深度是根节点到最近叶子节点的最短路径上的节点数。5.1 最小深度不是“最大深度的镜像版”很多人拿到最小深度的第一反应是“把 max 改成 min 不就行了”# 错误示范 def minDepth(self, root): if not root: return 0 left self.minDepth(root.left) right self.minDepth(root.right) return min(left, right) 1这个代码单独看好像没问题但它有一个致命缺陷对于一棵只有左子树、没有右子树的树右子树返回 0min 取 0那么结果就是 1。可是这棵树的最小深度真的是 1 吗不是。因为根节点不是叶子节点它还有左孩子真正的最近叶子节点在左子树上最小深度应该等于左子树的深度加 1而不是 1。问题出在空节点的含义上。空节点不能简单当作“深度为 0”因为在最小深度的定义里空节点不构成任何连向叶子节点的路径。空节点更像是一个“无效值”你需要跳过它只考虑非空子树的情况。5.2 递归正确写法分类讨论左右子树的存在性正确的写法需要区分三种情况左右子树都为空当前节点是叶子节点返回 1左右子树有一个为空最小深度取决于非空的那一侧返回非空子树的深度加 1左右子树都不为空取两者较小值加 1。def minDepth(self, root): if not root: return 0 if not root.left and not root.right: return 1 if not root.left: return self.minDepth(root.right) 1 if not root.right: return self.minDepth(root.left) 1 return min(self.minDepth(root.left), self.minDepth(root.right)) 1这个分类讨论比 max 版本多了几个分支是因为空节点的“语义”变了。在 max 中空节点是合法的 0你可以放心取 max但在 min 中空节点是一个陷阱你绝不能把 0 作为最小值参与比较否则任何只有单边子树的树都会错误地返回 1。仔细体会一下这题的价值——它提醒你在算法题里“定义”决定“实现”。你对“最小深度”的理解稍有偏差代码的结果就会出现系统性错误。面试官出这题很大概率就是在看你会不会忽略单边子树这种情况。5.3 迭代 BFS 解法遇到第一个叶子节点就返回最小深度用 BFS 迭代写其实比递归更直接。因为 BFS 是逐层扩展的你第一次遇到的叶子节点一定处于最小的层数此时返回当前深度计数即可。这个思路不需要像递归那样分类讨论逻辑非常干净。from collections import deque def minDepth(self, root): if not root: return 0 queue deque([(root, 1)]) while queue: node, depth queue.popleft() if not node.left and not node.right: return depth if node.left: queue.append((node.left, depth 1)) if node.right: queue.append((node.right, depth 1))这个解法用(root, 1)的形式把节点和深度打包存入队列每往下一层 depth 加一。当你访问到某个节点发现它没有左右孩子这个节点就是叶子节点直接返回当前 depth 就是最小深度。BFS 天然保证找到的第一个叶子节点一定在最小的层数这是深度优先遍历做不到的——DFS 可能会先走一条很深的路径浪费大量时间。如果你“比较较真”可能会问不用元组能不能只存节点用一个额外的 depth 变量可以但要注意由于 BFS 是逐层处理的每轮循环的节点深度相同所以也可以像前面“最大深度层序遍历”那样在每轮循环结束后 depth 1然后在进入下一轮循环之前检测是否存在叶子节点。元组法更直观也更省事扩展到其他需要携带额外状态的 BFS 题目时也更方便。6. 四道题合练通用模板与刷题复盘把四道题放在一起复盘你会发现它们的代码高度相似区别只在于返回值和终止条件的设计。这就是“刷树题组”的价值所在——帮你识别模式而不是孤立地记题目。6.1 四题解法对比表递归返回值设计与遍历顺序差异题目递归模板核心遍历顺序返回值类型关键难点LC 226 翻转二叉树交换 双递归先序 / 后序TreeNode注意不能中序LC 101 对称二叉树成对比较镜像位后序成对递归bool递归辅助函数两个参数LC 104 最大深度max(左右深度) 1后序int空节点返回 0LC 111 最小深度分类讨论单边子树后序 / 层序int空节点不能当 0 比较这四类返回值基本覆盖了二叉树递归题的主要返回类型返回修改后的树、返回布尔判断、返回数值统计。面试时拿到一道树题先判断返回类型再确定遍历顺序然后写终止条件这个流程可以应对 90% 的树题。6.2 关于递归写法的一些实战心得递归的代码虽短但真正想清楚每一步的执行过程还是需要花时间的。我最开始练习递归时有个笨办法在纸上把递归调用树画出来每次递归画一个圈回溯时画一条向上的箭头同时把返回值写在箭头旁边。画了好几棵树之后“递归就是函数调用自己、每一层有独立的状态、返回值逐层汇总”这个概念才算真正内化。另外一个有用的技巧是写递归时假想自己只能看到当前节点。不要去想“我这层的操作会怎么影响整棵树”专注于当前节点应该做什么操作、应该接收什么返回值、应该往上层返回什么。把这三个问题想清楚代码基本不会写错。很多人递归写不好就是因为脑子里总想着整棵树越想越混乱。调试递归还有一个现实的问题Python 默认的递归深度限制是 1000 层。在 LeetCode 上很多题目的树深不会超过这个限制但如果你自己造了一个极端测试用例比如一条 2000 层的链式树直接会抛RecursionError。遇到这种情况不是你的算法错了而是递归深度的工程限制。了解这个限制对于写生产代码很重要但在刷题阶段多数情况不用过度担心。6.3 二叉树题目的延伸方向正则化练习路径做完这四个题你可以继续沿着二叉树主线往两个方向扩展。第一个方向是“深度类问题”的延伸比如判断平衡二叉树LC 110本质上就是在求深度后加一个平衡性判断比如求二叉树直径LC 543需要在求深度的同时统计“经过某节点的最大路径长度”。这些题都复用最大深度的递归框架只是返回值增加了额外信息。第二个方向是“对称 / 翻转”类问题的延伸比如判断两棵树是否相同LC 100把“镜像比较”改成“直接比较”就行比如构造镜像树或二叉树的序列化与反序列化。翻转到对称这组题练完后你对“递归参数是两个节点”的写法会非常熟悉这种双参数递归在更多树题中比如最近公共祖先 LC 236有变体应用。做题的时候我习惯用一个简单的路径去强化记忆先从递归模板入手每道题都写出递归解法然后把其中一两题用迭代写法实现一遍体会两者在空间复杂度和代码风格上的差别。这样四道题做完你基本上把二叉树最基础也是最核心的套路全部过了一遍后续刷更复杂的树题会顺手很多。7. 常见问题排查单侧子树、空指针与返回值丢失这一节集中讲我做这四道题时实际踩过的坑以及读者私信问过我的高频问题。这些问题看着小但每一个都能让代码报错或者结果错误。7.1 单侧子树为什么是最大深度的陷阱最大深度的代码看起来简单但如果你稍微改一下把终止条件写成“没有左右孩子时返回 1”然后左右子树递归时不做空处理就会出问题。比如一棵只有左子树的链式树递归会沿着左子树一路往下走右子树每层都是 None你必须在递归到来时正确返回 0否则函数会在 None 上调用.minDepth()直接抛 AttributeError。这个问题的根源在于递归函数必须在进入递归体的第一行就处理空节点。很多人习惯先判断 root 是否为空再递归这是对的但要确保所有递归调用都经过了空节点检查。我的习惯是在一道树题的递归函数开头永远写一行if not root: return ...作为兜底这样后续代码就能放心使用 root 的属性而不用担心空指针。最大深度本身也有一个隐含的坑如果你把空树返回 0单节点树返回 1那么递归式max(left, right) 1就是安全的。如果你试图省掉空检查直接在 root 上调用maxDepth(root.left)那 root.left 为 None 时None 会传入函数函数的if not root就会兜住其实空检查本身已经写在函数开头了。这样反而没问题。真正错误的是在调用前对 None 做属性访问那才是空指针。7.2 递归返回值丢失的典型场景与定位技巧递归函数里最隐蔽的错误就是返回值丢失。以翻转二叉树为例有些人写完交换逻辑后忘记在函数末尾返回 root那么最终函数返回的就是 None。由于翻转操作是在原树上做的从 root 出发访问实际树时树已经被修改了看起来结果可能是对的。但是在对称二叉树的判断里如果你在递归比较时某个分支忘记把结果返回得到的就是 None而这会被外层当成 False导致对称判断失灵。这类问题的定位方式我总结了一个小技巧在递归函数末尾打一个临时打印输出当前节点的值和返回值。运行一个很小的测试用例对比打印结果和你手工推演的结果差异点在哪个节点哪里就出问题了。排查树题的错误用“小而精”的测试用例比大而全的用例更容易定位。7.3 层序遍历的队列首元素弹出性能Python 的列表pop(0)是一个 O(n) 操作因为弹出头部元素后剩余元素需要整体往前挪一位。在层序遍历里如果你用pop(0)处理一棵节点数上万的树性能会明显变差。正确做法是用collections.deque它的popleft()是 O(1)。这虽然是个小点但在我写 BFS 版本的层序遍历时被面试官专门指出过后来我就养成了一个习惯凡是要用队列的地方一律用 deque不再用列表模拟队列。另一个队列相关的小建议是在迭代 BFS 里如果要记录每个节点对应的层数或路径用元组入队最直观。但在内存敏感的代码中元组的开销要略高于单独维护一个数组这时候可以根据场景选择维护一个“层数数组”并与节点索引对应或者使用两个队列分隔节点和深度。在 LeetCode 题目的数据规模下元组方案完全够用可读性也更好。7.4 测试用例设计从一棵树到多棵树刷这四道题时我建议你用几个固定测试用例来验证代码一棵空树验证空节点返回逻辑一棵只有根节点的树验证叶子节点的返回逻辑一棵普通的三层满二叉树验证一般情况的递归正确性一棵只有左子树的链式树或者只有右子树专门测最小深度和单边子树问题一棵左右子树深度不同的树验证最大深度的 max 逻辑。这种“边界 常规 极端”的测试思路不仅适用于树题适用于任何算法题。LeetCode 虽然自带测试用例但自己主动构造边界条件能更早发现代码的脆弱点。8. 四题之外的延伸思考从模板到举一反三这四道题练完你可能会觉得“树的题好像也没那么难”。这个感觉是对的但要注意它是因为你把基础模式吃透了。四题之外的进阶题比如“二叉树最近公共祖先”“二叉树的序列化与反序列化”“二叉树的最大路径和”都是在基础模板上添加状态处理或返回值语义拓展。8.1 双参数递归从对称二叉树到最近公共祖先对称二叉树用到的是isMirror(left, right)这种双参数递归。这个模式在后续的树题中非常常见。比如最近公共祖先LCA问题你需要在一个递归函数里同时处理两个目标节点的查找返回值可以是“找到的节点”或者“空”。从“单参数遍历”到“双参数比较”的跃迁本质上是递归的输入状态从“一棵子树”扩展到了“两个子树的对应位置”理解了对称二叉树的isMirrorLCA 的分支逻辑就不难接受。8.2 深度类问题的统一框架从最大深度到直径问题最大深度max(left, right) 1这个框架可以无缝对接到二叉树直径问题。直径的定义是“任意两节点间最长路径的边数”它等价于经过某个根节点的左子树深度加右子树深度。你在递归求深度的过程中顺便用一个全局变量记录left right的最大值最后返回的全局变量就是直径。这类“递归计算主返回值 全局变量辅助记录额外信息”的模式是很多高级树题的通用解法。建议你在做完最大深度后立刻尝试一道直径题能加深对这个模式的理解。8.3 思考题如果再加一个“最大直径”和“平衡判断”把题目延伸一下LC 110 平衡二叉树本质上就是“左右子树深度差不超过 1”这可以复用最大深度的递归在返回值之外用一个全局标记记录是否平衡。LC 543 二叉树直径需要返回的不仅是节点深度还要考虑左右子树深度之和的最大值。这些题本质上都在问同一个问题——“你能否在递归过程中额外携带并维护状态”。这些状态可以是最大值、最小值、布尔值、或者是另一个节点的引用。掌握了这个“额外状态携带”的思路你在树这个专题上的能力会比只刷几道基础题提升一个量级。我在实际刷题中有一个体会树题的提升速度不太靠大量刷题靠的是反复咀嚼少数题的递归结构和状态设计。今天这四道题恰好覆盖了“修改结构”、“比较结构”、“统计深度”三种返回语义你把它们的异同吃透比囫囵吞枣做出二十道题更有收获。