★ FEATURED ARTICLE 今天是我算法复健的第12天照例刷了四道 LeetCode 二叉树题226 翻转二叉树、101 对称二叉树、104 二叉树的最大深度、111 二叉树的最小深度。这四道题不是随手点的它们摆在一起恰好能把二叉树最核心的递归遍历吃透——前序、后序、层序都覆盖到了还顺手解决了一个面试高频坑点最小深度和最大深度写法上的区别。如果你也是刚开始系统刷树或者刷到中等难度题时总觉得递归写不明白我建议你先花一天时间把这四道题做扎实性价比非常高。为什么这么说因为二叉树这块的题翻来覆去就绕着“遍历”走遍历顺序决定了解题思路递归模板决定了解题速度。今天这四道题里226 是典型的前序遍历应用101 是后序遍历的经典代表104 和 111 则既能用递归也能用层序玩出花。做完之后你会发现所谓“算法复健”很多时候就是把这种最基础的模式重新刻进肌肉记忆里。1. 为什么选这四道题作为一组1.1 四道题的内在联系我刷题有个习惯不按题号随机刷而是按“一题吃透一个模式”的方式分组。今天这组题的目的非常明确——它们都属于“暴力递归 遍历模板”就能解的入门友好题但又各自带了不同的尾巴。LC 226 翻转二叉树核心是交换左右孩子相当于前序遍历的位置上做操作。LC 101 对称二叉树核心是同时递归两棵子树比较“外侧对外侧、内侧对内侧”本质是后序遍历的变体。LC 104 最大深度核心是分解成“左子树深度 右子树深度 1”标准后序。LC 111 最小深度表面上是 104 的对称写法实际上藏着递归条件的陷阱属于“看起来很简单的送分题一写就错”。这四道题如果只是分别做一遍你会觉得它们很简单但如果把它们的代码并排放在一起看就能发现一个共同的骨架——递归函数 终止条件 单层逻辑。所以我说这一组是“遍历顺序的集中训练”比东刷一道西刷一道有效得多。1.2 做题前的基础约定先说清楚后面代码的基础环境。我用的是 CTreeNode 定义保持 LeetCode 默认结构struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} };另外你最好先接受一个观念递归函数不要把“返回值和中间逻辑”搞混。下面四道题里有的递归函数需要返回 TreeNode*226有的需要返回 bool101有的返回 int104、111。返回类型不同单层递归逻辑就完全不同。2. 二叉树递归的万能模板2.1 为什么递归能通吃二叉树二叉树本身就是递归定义的结构一棵二叉树要么是空树要么是“根节点 左子树 右子树”而左右子树又各自是一棵二叉树。所以处理二叉树的很多问题天然适合用递归——你不需要手写一个显式的栈来模拟系统栈只要让函数自己跟自己玩就行。我经常跟朋友说递归别去“人肉跟踪”每一层那样三层以上就晕了。你只需要抓住三件事函数是干什么的、什么时候不干了、单层怎么递给上一层。剩下的交给系统栈。2.2 递归三要素以“翻转二叉树”为例三个要素是这样拆的函数参数和返回值参数是当前节点 root返回值是翻转后的子树根节点。终止条件root 为空直接返回空。单层逻辑交换左右孩子然后递归翻转左子树、右子树。这套模板看起来简单但很多人写错就错在第 2 步和第 3 步的顺序上——是先交换再递归还是先递归再交换226 这道题两种都能过但换成中序就不行了我在第 3 节会专门讲这个坑。2.3 遍历顺序的选择逻辑二叉树的递归遍历有前序、中序、后序三种顺序对应的是“处理根节点”的位置遍历方式单层执行顺序典型用途前序处理当前节点 - 左递归 - 右递归翻转、构造、从上往下传值中序左递归 - 处理当前节点 - 右递归BST 升序输出、按值操作后序左递归 - 右递归 - 处理当前节点求深度、比较子树、从下往上收集信息今天四道题里226 用前序更直观101 必须用后序因为要先拿到左右子树的比较结果才能返回 true/false104 和 111 用后序求深度。记住一个直觉如果当前节点的结果依赖左右子树的结果那就选后序如果当前节点的操作要先做完再处理孩子那就选前序。3. 逐题拆解与代码实现3.1 LC 226 翻转二叉树题目意思是把一棵二叉树所有节点的左右孩子都交换相当于把树翻个面。这道题的入口很浅核心操作就一个swap。我习惯的递归写法TreeNode* invertTree(TreeNode* root) { if (root nullptr) return root; swap(root-left, root-right); invertTree(root-left); invertTree(root-right); return root; }注意我采用的是“先交换再递归”。这里的前序遍历逻辑很清晰处理完当前节点的交换后它的左右孩子已经对调了所以接下来递归root-left时实际递归的是“原来的右子树”。如果你把顺序反过来先递归再交换也能 ACTreeNode* invertTree(TreeNode* root) { if (root nullptr) return root; invertTree(root-left); invertTree(root-right); swap(root-left, root-right); return root; }这相当于后序翻转。很多人会问那中序行不行答案是不要用中序。中序的顺序是左、根、右当你翻转完左子树回到根节点交换左右孩子再 “递归右子树” 的时候右边其实已经是原来的左子树等于把同一个子树又翻了一遍最后结果等于没翻。这道题也可以层序做用队列一层层遍历节点每个节点出队时都 swap 一下左右孩子。我觉得递归版最方便理解但如果你面试被要求写非递归版层序更不容易出错。3.2 LC 101 对称二叉树对称二叉树的定义通俗点说就是“树沿根节点竖直对折两边完全重合”。这一题很多人第一反应是单树递归就是先判断根节点左右孩子是否相等再判断左右子树是否对称。问题在于对称的判断需要跨子树比较根节点的左子树要和右子树比左子树的左孩子要和右子树的右孩子比左子树的右孩子要和右子树的左孩子比。所以我更愿意把它改写成“两棵树是否镜像相等”。递归函数的参数就从单指针变成双指针class Solution { public: bool isSymmetric(TreeNode* root) { if (root nullptr) return true; return compare(root-left, root-right); } 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; } };终止条件为什么要把“都为空”和“一个为空”分开写因为都为空时说明这个分支到底了是对称的一个为空一个不为空直接就能判定不对称不需要再递归下去了。这题之所以是后序遍历就是因为当前节点的对称结果取决于左右子树各自的“外侧”和“内侧”比较结果必须先递归回来才能做与运算。你一定要体会这种感觉后序不是“不能在前面做操作”而是“操作必须等孩子的结果”。对称这种判断天然契合后序。类似的还有“判断两棵二叉树是否相同”核心也是一个双指针递归一个比较 left 和 left一个比较 right 和 right。对称树只是把比较对象换成了外侧和内侧代码结构几乎不变。3.3 LC 104 二叉树的最大深度最大深度的定义是从根节点到最远叶子节点的路径节点数。我一般直接说“树的层数”。递归写法特别简单int maxDepth(TreeNode* root) { if (root nullptr) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return 1 max(leftDepth, rightDepth); }可能有人会有疑问为什么空节点返回 0那叶子节点不就是 0 1 1没错逻辑就来自这里。这题的递归顺序是后序先把左右子树的深度算出来取较大值再加 1就是当前节点的深度。不过我一直觉得最大深度用层序遍历来做思路更加贴脸。层序遍历天然是一层一层走的只要你统计遍历了多少层那就是最大深度int maxDepth(TreeNode* root) { if (root nullptr) return 0; queueTreeNode* que; que.push(root); int depth 0; while (!que.empty()) { int size que.size(); depth; for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); if (node-left) que.push(node-left); if (node-right) que.push(node-right); } } return depth; }这里的坑是size que.size()必须在 for 之前固定下来不能写成i que.size()因为队列在遍历过程中会不断 push 新节点size 会变化。很多初学者在这里翻车队列越扩越大层数统计自然就错了。3.4 LC 111 二叉树的最小深度最小深度这题就是今天的主角它看起来就是 maxDepth 的镜像把 max 换成 min 不就行了先看错误写法int minDepth(TreeNode* root) { if (root nullptr) return 0; return 1 min(minDepth(root-left), minDepth(root-right)); }这么写对于“一路到底都是满节点”的树没问题但遇到单子树就会立刻出错。举个最经典的例子根节点只有左子树右子树为空。按照上面的写法右子树返回 0左子树返回它的深度min 取 0结果最大也就 1。但真实的最小深度应该是左子树的深度加 1因为右子树那个方向根本不存在叶子节点不能算一条有效路径。最小深度的准确定义是根节点到最近叶子节点的距离。空指针不是叶子所以空分支不能参与 min。正确递归写法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 1 min(leftDepth, rightDepth); }关键就在于只有当左孩子存在时才递归左子树右孩子同理。如果某一侧为空就保留 INT_MAX让它不参与比较这样单子树的情况就能正确处理了。同样这题也可以用层序做而且层序写出来会更自然从根节点开始一层层扫遇到第一个左右孩子都为空的节点直接返回当前深度。这个思路其实对应了“广度优先搜索找到最短路径”的直觉我特别喜欢这个版本因为它天然规避了递归里的边界条件int minDepth(TreeNode* root) { if (root nullptr) return 0; queueTreeNode* que; que.push(root); int depth 1; while (!que.empty()) { int size que.size(); for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); if (node-left nullptr node-right nullptr) { return depth; } if (node-left) que.push(node-left); if (node-right) que.push(node-right); } depth; } return depth; }这个版本我建议你亲手敲一遍因为“遇到叶子就返回”这个提前退出逻辑是很多更复杂的图论问题的基础思想。4. 这四道题的迭代解法与统一思路4.1 用栈模拟递归的统一写法递归本质上是用系统栈如果你想做非递归版本最常见的方法是显式定义一个栈。以 226 翻转二叉树为例用栈模拟前序TreeNode* invertTree(TreeNode* root) { if (root nullptr) return root; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); swap(node-left, node-right); if (node-left) st.push(node-left); if (node-right) st.push(node-right); } return root; }注意入栈顺序因为栈是先进后出如果你希望左子树先被处理就要先把右子树压栈。这里因为交换之后左孩子变成原来的右孩子右孩子变成原来的左孩子所以先压 left 再压 right出来的时候先处理 right 再处理 left效果是一样的。这个细节很多人面试时会卡一下。对称二叉树 101 也可以用栈或者队列迭代做法是成对入队或入栈每轮取两个节点出来比较bool isSymmetric(TreeNode* root) { if (root nullptr) return true; queueTreeNode* que; que.push(root-left); que.push(root-right); while (!que.empty()) { TreeNode* leftNode que.front(); que.pop(); TreeNode* rightNode que.front(); que.pop(); if (leftNode nullptr rightNode nullptr) continue; if (leftNode nullptr || rightNode nullptr) return false; if (leftNode-val ! rightNode-val) return false; que.push(leftNode-left); que.push(rightNode-right); que.push(leftNode-right); que.push(rightNode-left); } return true; }这个思路好在非常直观每一对入队出队的节点都应该是对称位置上的一对“兄弟”。只要有一对不匹配整棵树就不是对称的。这种成对处理的思想在后续很多“比较两棵树”的题目里都通用。4.2 深度题目的层序遍历统一解104 和 111 的迭代解法我在上一节已经各给了一个层序版本。可以说一旦你把层序遍历模板写熟了最大深度、最小深度、右视图、层平均值、N 叉树层序遍历全部是同一道题。模板就是根节点入队外层循环处理每一层内层循环用固定 size 处理当前层的节点操作节点把非空孩子入队这个模板的稳定性非常高。相比递归它不需要考虑系统栈溢出也不容易被单子树情况坑到。唯一的代价是代码稍微长一点。5. 常见问题与排查技巧实录5.1 为什么写二叉树程序时总报运行时错误这是热词里非常真实的一个问题。我在帮助朋友排查时发现九成“运行时错误”都是空指针解引用。具体到今天的四道题最容易发生的场景有两个第一个是在递归里没有判空就访问root-left。比如有人写对称二叉树时直接compare(left-left, right-left)却忘了 left 或 right 可能为空于是一层递归进去就崩了。第二个是在迭代写法里从队列或栈里弹出节点后直接访问node-val完全没有考虑 nullptr 的可能。提醒不管递归还是迭代拿到一个节点后的第一反应应该是“它是不是空”。判空的顺序也很重要比如对称树里left nullptr || right nullptr和left-val ! right-val的顺序不能颠倒否则同样会有空指针风险。5.2 最小深度写成最大深度的“照抄”版这个坑我在 3.4 里已经详细说了。很多人刷到 111 时习惯性地把 104 的max换成min提交之后发现错一大片。问题不在于你不会递归而在于你没有从定义出发去理解“叶子节点”和“空节点”的区别。有一个简单的口诀可以帮你记住最大深度随便走空分支当作 0 参与比较没问题最小深度必须挑叶子空分支没有资格参与比较。如果你用递归处理最小深度也可以不写 INT_MAX改成分开判断int minDepth(TreeNode* root) { if (root nullptr) return 0; if (root-left nullptr root-right ! nullptr) { return 1 minDepth(root-right); } if (root-left ! nullptr root-right nullptr) { return 1 minDepth(root-left); } return 1 min(minDepth(root-left), minDepth(root-right)); }这个写法的意图更直白单子树时只能走存在的那一侧只有当两侧都存在时才取最小值。我觉得这个版本比 INT_MAX 版本更适合新手理解。5.3 递归返回条件写错导致的死循环还有一种常见错误是递归终止条件写得不对比如翻转二叉树里如果忘记写if (root nullptr) return root;当递归到空节点时会尝试访问空指针的成员直接崩溃。或者对称二叉树里把“都为空返回 true”漏掉就会发生无限递归因为两个空指针会一直互相递归下去最后栈溢出。排查这类问题有个笨但有效的办法在小规模用例上手动走一遍。比如一棵只有三个节点的树根节点 1左孩子 2右孩子 2。你手动模拟一下递归调用就能知道是哪一层出了问题。不用模拟太深三层以内基本能定位出逻辑错误。5.4 四道题的易错点速查表题号核心考点最容易踩的坑226前序/后序交换左右孩子中序写法会把同一棵子树翻转两次101双指针递归、内外侧比较忘记判断空节点比较对象写错104后序求高度、层序统计层序循环里size被动态更新111叶子定义、单子树处理直接套min导致单子树返回 16. 一些实际复健过程中的经验四道题做完我自己最大的收获并不是代码而是对“递归函数到底在返回什么”有了更清醒的认识。以前我刷二叉树总喜欢盯着某一步的局部变化看结果经常绕晕在递归里。现在我的习惯是先给函数定好“契约”——它接收什么、返回什么、调用后保证什么效果。然后单层逻辑严格按照这个契约写递归自然就清晰了。另外想分享一个小技巧这几道题做完之后可以顺手再去刷三道题巩固同一种模式。如果是 226 的延伸翻转二叉树后判断两棵树是否相同。如果是 101 的延伸判断一棵树是否是另一棵树的子树。如果是 104 和 111 的延伸求二叉树的最小公共祖先。这些题目本质上都还在用今天练熟的递归框架只是参数和终止条件稍微变通一下。刷算法最忌讳每次遇到新题都觉得“没见过”实际上把今天这四道题的模板吃透你会发现一大片中低难度的二叉树题都长一个样。最后再说一句算法复健是场持久战别指望一天吃成胖子。我给自己定的目标就是每天一组小规模题目做完把代码重新抄一遍再把错误点记录下来。坚持到 Day 12 之后最明显的变化是写递归代码的时候手更稳了不再去手动跟踪每一层调用。如果你也正在复健或者刚开始刷 LeetCode希望你也能从这组最简单的二叉树题里找到这种“手稳”的感觉。
阅读完成 · 觉得有帮助？
