二叉树递归三板斧：翻转、对称、最小深度一次讲透

训练营第12天三道题摆在一块儿的时候我明显感觉到递归法在二叉树题目里那种“绕不开”的存在感226.翻转二叉树、101.对称二叉树、111.二叉树的最小深度题目看起来一个比一个短但每一道都在逼你想清楚递归的终止条件、返回值和单层逻辑。尤其是最小深度那道题我第一次提交就被[1,null,2]这种链表形态的树给坑了错得心服口服。这篇文章就把这三道题一次说透。我会从思路拆解讲到代码实现再到我实际刷题时踩过的坑和排查方法适合刚学完二叉树遍历、正准备刷递归法题目的同学。如果你已经被“写递归函数”这件事折磨过或者写过Runtime Error但死活找不到原因这篇内容应该能帮你少走不少弯路。1. 为什么是这三道题递归法在二叉树里的“三板斧”刷题不能只盯着题目本身。代码随想录把这三道题放在同一期训练营里是有意的安排——它们分别考察了递归法的三种典型用法对子树做修改、对两棵子树做比较、对子树深度做累计。这三板斧覆盖了绝大多数二叉树递归题的底层逻辑。1.1 递归法的“三要素”必须先刻在脑子里写递归题之前先把这套框架过一遍第一终止条件是什么比如节点为空、节点是叶子、已经找到目标第二返回值是什么是处理后的节点指针还是一个布尔值还是一个整数深度第三这一层递归要完成什么操作比如交换左右节点、比较两个节点值、计算左右子树深度。很多时候卡题不是思路不清楚而是这三个问题没有在动手前回答完。以翻转二叉树为例终止条件是空节点直接返回返回值应该是翻转后的当前节点指针单层逻辑就是交换左右孩子再递归翻转左右子树。这个框架一旦定下来代码基本就是照着填空。对称二叉树则是返回值变成布尔值终止条件要同时考虑两个节点的四种情况。到了最小深度返回值变成整数终止条件还多了一个“遇到叶子节点就返回1”的判断。三道题恰好覆盖了三种返回类型这就是训练营这样排期的深意。1.2 二叉树的遍历顺序决定了递归的写法递归法和二叉树的遍历顺序是死死绑定在一起的。前序遍历是“先处理当前节点再递归孩子”中序遍历是“先左、再中、再右”后序遍历是“先递归孩子再处理当前节点”。翻转二叉树用的是前序或后序对称二叉树本质上依赖后序的“由下而上汇总”最小深度则需要左、右子树的信息都回来之后才能做决策。这也是为什么很多人写翻转二叉树时会把中序遍历写上结果发现树“翻完又翻回来了”。中序遍历在遍历完左子树之后处理当前节点此时交换左右孩子但接下来代码要遍历的是“右孩子”而它已经被换成了原来的左子树——这个左子树刚刚才被翻转过一次于是就会出现一部分节点被翻转两次、一部分始终没翻的情况。后面我会专门展开讲这个坑。1.3 这一期和前后题目怎么衔接这三道题做完之后你会发现自己看后续题目的眼光变了。比如后面做104.二叉树的最大深度时你拿到的代码和最小深度几乎一模板一样做112.路径总和时你会意识到它也是递归返回值当判断用的典型场景做236.二叉树的最近公共祖先时你会体会到“后序遍历返回值”的组合拳有多爽。可以说这三道题是二叉树递归法的地基今天多花点时间把细节抠清楚后面会省很多事。2. 226.翻转二叉树最直观的递归入门题这道题在LeetCode上叫Invert Binary Tree翻转一棵二叉树意思就是每个节点的左右孩子全部交换。题目一句话但实现的细节并不像描述那么随意。我第一次交的时候用的中序遍历结果翻了个寂寞后来才明白问题出在遍历顺序上。2.1 解题思路与前序后序的选择翻转一棵树操作对象是每个节点的左右孩子指针。最直接的逻辑对于当前节点先把它的left和right换掉然后递归翻转左子树再递归翻转右子树。这就是前序遍历的写法——先处理自己再处理孩子。TreeNode* invertTree(TreeNode* root) { if (root nullptr) return nullptr; swap(root-left, root-right); invertTree(root-left); invertTree(root-right); return root; }这段代码为什么是对的因为swap交换的是当前节点的两个孩子指针交换完之后左孩子指针指向的是原有的右子树右孩子指针指向的是原有的左子树。接下来递归调用invertTree(root-left)处理的实际是原来的右子树再递归invertTree(root-right)处理的是原来的左子树。这样一来每一棵子树都只被处理一次翻转正确。换成后序遍历也同样可行先递归翻转左子树再递归翻转右子树最后交换两个已经翻转完成的子树。这两种顺序都没有问题因为对每个节点来说交换操作和递归操作互不干扰。但中序遍历为什么不行我把代码写出来给你看// 错误的写法中序遍历翻转 TreeNode* invertTree(TreeNode* root) { if (root nullptr) return nullptr; invertTree(root-left); swap(root-left, root-right); invertTree(root-right); return root; }这段代码的执行过程很微妙。以一棵只有三层的小树为例先递归翻转左子树左子树被正确翻完了回到根节点交换左右孩子此时根节点的右孩子是“原来的左子树”——它已经被翻转过一次了。代码接着递归处理root-right等于把这个已经翻转过的子树又翻了一遍而根节点“原来的右子树”被换到了左边压根没有进入递归。结果就是有些子树被翻了两次有些子树一次都没被翻。画个图模拟一下就会看得非常清楚。2.2 交换节点的一个小细节很多C初学者在写交换时会习惯性地写一个临时变量TreeNode* temp root-left; root-left root-right; root-right temp;这样写完全没问题只是std::swap更简洁。但这里有一个容易被忽略的点swap交换的是指针的值不是TreeNode对象本身。也就是说我们改的是当前节点的left和right成员整棵树的内存结构并没有复制。空间复杂度是递归栈的深度而不是复制一棵树的开销这一点心里要有数。2.3 用层次遍历迭代法也能翻转递归法写起来丝滑但如果你想换个思路层次遍历同样可以完成翻转用队列存节点出队一个节点就交换它的左右孩子再把非空孩子入队。这个做法本质上和递归一样每个节点只处理一次只是把递归栈换成了显式队列。建议把两种解法都写一遍因为后面很多二叉树题目你都需要在“递归”和“迭代”之间灵活切换。from collections import deque def invertTree(root): if not root: return None q deque([root]) while q: node q.popleft() node.left, node.right node.right, node.left if node.left: q.append(node.left) if node.right: q.append(node.right) return rootPython写起来更短关键就一行的node.left, node.right node.right, node.left。不管用什么语言思路是一样的每个节点必须且只能被翻一次。3. 101.对称二叉树用递归同时比较两棵子树翻转二叉树之后紧接着来了一道“镜像”题。对称二叉树要求判断一棵二叉树是不是镜像对称的也就是说根节点的左子树和右子树从外到内、从内到外都要一样。比如[1,2,2,3,4,4,3]是一棵对称树而[1,2,2,null,3,null,3]不是。这道题的难点在于你不能再盯着单个节点看而要同时拿两个节点来比。3.1 为什么这道题要用“后序”思维初看这道题很多人会想我是不是可以递归左子树和右子树分别判断它们是不是对称树这个思路是错的。一棵树的左子树本身可能非常不对称但只要它的镜像能和右子树对应上整棵树依然是对称的。关键不在“单棵子树长什么样”而在“两棵子树拼在一起成不成镜像”。所以递归函数的参数应该是两个节点left和right。判断逻辑分成四步这种分步思考的方式对新手特别友好两个节点都为空说明这一层匹配返回true一个为空一个不为空说明结构不对称返回false两个都不为空但值不相等返回false两个都不为空且值相等继续往下比left.left和right.right比外侧left.right和right.left比内侧。第四步为什么要分“外侧”和“内侧”你可以想象一面镜子放在根节点上左子树的左孩子对应的是右子树的右孩子左子树的右孩子对应的是右子树的左孩子。方向反了镜像就不成立。代码里必须先递归调用外侧和内侧再把两个布尔结果合并返回这就是典型的后序遍历思路——先收集子树的信息再对当前层做判断。如果你先 return后面的递归就不会执行整个判断就不是完整的。bool compare(TreeNode* left, TreeNode* right) { if (left nullptr right nullptr) return true; else if (left nullptr || right nullptr) return false; else if (left-val ! right-val) return false; bool outside compare(left-left, right-right); bool inside compare(left-right, right-left); return outside inside; } bool isSymmetric(TreeNode* root) { if (root nullptr) return true; return compare(root-left, root-right); }3.2 注意别和“搜索二叉树”的概念混淆刷题时有个热词叫搜索二叉树BST特别容易和对称二叉树混在一起。BST 的定义是左子树所有节点值小于根节点右子树所有节点值大于根节点并且左右子树本身也是BST。但是对称二叉树完全不关心值的大小顺序只关心左右两边是不是镜像。一棵BST可以是完全不对称的比如[2,1,3,null,null,4,5]不是对称树但它完全可以是合法的BST。做这一题的时候别用“左小右大”的思维去套会把自己绕晕。3.3 用队列做迭代版本同一个套路两种写法对称二叉树也可以用迭代法实现。思路是用队列成对地把节点放进去。先放左孩子和右孩子出队两个节点进行比较再把left-left和right-right放进去把left-right和right-left放进去。这里的顺序不能乱因为镜像比较的逻辑和递归是完全一致的。迭代法唯一的区别是把递归栈换成了队列好处是避免了递归过深时的栈溢出风险坏处是代码可读性稍微差一点。两种写法建议都掌握。from collections import deque def isSymmetric(root): if not root: return True q deque([root.left, root.right]) while q: left q.popleft() right q.popleft() if not left and not right: continue if not left or not right or left.val ! right.val: return False q.append(left.left) q.append(right.right) q.append(left.right) q.append(right.left) return True这里要注意continue和return False的区别。两个节点都为空时说明这一层匹配完成但队列里可能还有下一层的节点所以要继续循环只有出现“一个为空一个不为空”或“值不相等”时才可以提前判死刑。4. 111.二叉树的最小深度递归法最容易翻车的边界题第三道题是求最小深度题目定义是从根节点到最近叶子节点的最短路径上的节点数量。叶子节点指的是没有孩子的节点。别看这道题只是一道深度题它是我这三道里唯一提交失败过的失败原因就是没有理解“叶子节点”这个限制。4.1 最大深度与最小深度的关键差异求最大深度代码人人都能背下来return max(maxDepth(root-left), maxDepth(root-right)) 1;如果照葫芦画瓢写最小深度很容易写出return min(minDepth(root-left), minDepth(root-right)) 1;这行代码放在一棵正常的满二叉树里结果可能碰巧是对的。但一旦遇到[1,null,2]这种只有右子树没有左子树的情况就会力出问题根节点的左孩子为空minDepth(nullptr)返回0右孩子是节点2minDepth(node2)返回1整体结果是0 1 1。可是真实的树长这样1 → 2从根节点到叶子节点2的路径上明明有2个节点最小深度应该是2不是1。问题就出在null不是叶子节点。一棵树如果只有右孩子左孩子的空指针根本不能算作一条“有效路径”的终点。所以必须分清楚左子树为空时要走右子树右子树为空时要走左子树两边都为空时说明当前节点就是叶子节点返回1。4.2 正确的递归写法与分类讨论把逻辑落到代码上最简单的方式是分情况讨论int minDepth(TreeNode* root) { if (root nullptr) return 0; // 当前节点是叶子节点 if (root-left nullptr root-right nullptr) return 1; int leftDepth INT_MAX; int rightDepth INT_MAX; if (root-left) leftDepth minDepth(root-left); if (root-right) rightDepth minDepth(root-right); return min(leftDepth, rightDepth) 1; }这段代码的巧妙之处在于把左右深度都初始化为INT_MAX只递归存在的子树。如果当前节点只有左子树那么右子树不参与比较leftDepth是左子树的真实最小深度整体返回leftDepth 1如果两个子树都不存在说明当前是叶子直接返回1。这种写法把所有情况都统一到了min里不需要再额外写if (root-left)分支去递归判断代码更清晰。也可以写成更直白的版本int minDepth(TreeNode* root) { if (root nullptr) return 0; if (root-left nullptr root-right nullptr) return 1; if (root-left ! nullptr root-right nullptr) return minDepth(root-left) 1; if (root-left nullptr root-right ! nullptr) return minDepth(root-right) 1; return min(minDepth(root-left), minDepth(root-right)) 1; }两种写法结果一模一样你可以选自己更容易接受的版本。我个人的建议是第一次做这道题时老老实实分四种情况写一遍把边界条件想透了之后再改成INT_MAX的简洁写法这样不容易翻车。4.3 迭代法为什么更适合这道题使用层序遍历求最小深度其实更直观。因为层序遍历是一层一层往下扫的当第一次遇到一个叶子节点时当前的深度就是最小深度直接返回即可不需要把整棵树都扫完。而递归法不管三七二十一要把所有分支都算一遍浪费的时间在极端情况下可能是指数级的。int minDepth(TreeNode* root) { if (root nullptr) return 0; queueTreeNode* q; q.push(root); int depth 0; while (!q.empty()) { int size q.size(); depth; while (size--) { TreeNode* node q.front(); q.pop(); if (node-left nullptr node-right nullptr) { return depth; } if (node-left) q.push(node-left); if (node-right) q.push(node-right); } } return depth; }如果面试时时间紧张建议先写层序遍历因为它不容易出现边界条件的坑如果面试官要求用递归法再切换到上面的分类讨论写法。两种方式都能过但背后的思维模式完全不同这也是算法训练营反复建议“一题多解”的原因。5. 常见错误与排查技巧递归写错时如何快速定位刷这三道题时我遇到过编译报错、逻辑错误、运行超时甚至还有一次直接遭遇了Stack Overflow。这些错误本身不可怕可怕的是不知道从哪里下手排查。这里分享一下我的排查方法以及写递归代码时最容易犯的几个错。5.1 运行时错误是怎么来的先看一个最典型的场景你写翻转二叉树时递归调用了invertTree(root-left)但忘记写终止条件或者终止条件写了if (root-left nullptr) return root;。这种条件下递归到空节点时根本进不了函数体判断代码会继续访问root-left的空指针最终触发空指针访问或栈溢出。这类问题在LeetCode上报出来就是Runtime Error。再比如对称二叉树很多人写终止条件时习惯于先检查left-val ! right-val却忘了先判断左右是否为空。一旦left是空指针left-val直接越界。正确顺序一定是先判空再判值。这个顺序在写递归时是铁律任何非空指针的成员访问都要放在判空之后。另外一个隐蔽的坑是递归函数写成了死循环。最小深度那道题如果你在某个分支里递归调用自己却没改变传入的参数会导致同一个节点被无限递归。调试的时候会发现程序一直不退出CPU占用率飙升。这种情况一般是单层逻辑写错了检查一下递归参数是否真的“更小了一层”。5.2 调试技巧用打印法看清递归过程我强烈推荐一个土办法在递归函数开头加一行打印输出当前节点值和深度。比如翻转二叉树可以在进入函数时打印swap node: to_string(root-val)运行一遍你就能看到递归访问节点的顺序从而判断自己的遍历顺序是不是想要的。void debug(TreeNode* root, int depth) { if (root nullptr) return; cout string(depth * 2, ) root-val endl; debug(root-left, depth 1); debug(root-right, depth 1); }通常跑一个只有三四个节点的小测试用例就够了。如果打印出来的顺序和预期不符那问题多半出在递归调用的顺序上如果打印过程出现重复节点那就说明出现了交叉引用或翻转了两次的“中序陷阱”。这个方法比我靠肉眼盯代码高效十倍强烈建议在无助的时候先用起来。5.3 别掉进“人肉递归”的坑写这三道题时我发现自己最常犯的毛病是想在脑子里把递归的调用栈完整过一遍。每次遇到递归就自己模拟一遍“进去、返回、再进去”很快就晕了。后来我总结了一个经验递归函数本身应该被当作一个已经正确实现的黑盒你只需要保证三件事终止条件正确返回值类型统一单层逻辑不会改变传入参数的约束。写完这三条剩下的交给递归自身去处理。打个比方你写minDepth(root-left)时不需要再问自己“这个函数是怎么一步步算出来的”你只需要知道它返回的是左子树的最小深度。这种信任思维是递归代码能写对的前提。如果发现结果不对再来检查三要素而不是逐行展开整个递归过程。5.4 题目之间的迁移技巧三道题做完之后把它们放在一起复盘会发现一个规律只要是“求深度、求路径、判断形态”这类二叉树问题递归法的核心都在于如何用返回值表达子问题的结果。翻转二叉树返回的是处理后的节点对称二叉树返回的是布尔判断最小深度返回的是整数深度。想清楚返回值再想递归逻辑大方向就不会偏。另外如果你想把层序遍历练熟我建议把这三道题全部用迭代法再做一遍。尤其是最小深度用层序遍历实现会简单到让人怀疑是不是同一道题。用“先递归再迭代”的双解法去刷题比只背一种答案扎实得多这也是代码随想录训练营一贯的风格。写在最后我的三点实操体会训练营第十二天这三道题我实际刷下来的感受是题目难度真的不算大但每道题都精准击中了一个容易忽略的细节。翻转二叉树提醒你遍历顺序的重要性对称二叉树逼迫你从“单个节点”的思维跳到“两棵子树”的思维最小深度则是把空指针和叶子节点的概念差异变成了一道送命题。如果你正在刷这一期的题我建议你按照这个顺序来先独立写三要素再写代码最后故意用错误的写法提交一次看看输出错在哪里。比如把最小深度写成min(left, right) 1提交之后观察失败用例你就能彻底理解为什么空子树不能参与最小值的比较。这种“故意犯错再纠正”的方式比我单纯看题解的记忆要牢固得多。我自己做题最大的收获是学会了“信任递归”。不要把递归想成一种需要实时跟踪的复杂调用而是要像使用库函数一样信任它的返回值。当你能写出简洁的递归停止条件并且清楚地知道每一层返回什么二叉树这一大类题目就算真正上道了。