1. 先把五行代码的“血缘关系”理清楚刷LeetCode的朋友应该都有过这样一种体验今天刷了144题前序遍历AC了感觉很简单明天做94题中序遍历也AC了觉得不过如此后天碰到145题后序遍历顺手就写完了——然后第102题层序遍历直接懵了第111题最小深度又开始怀疑自己到底懂不懂二叉树。这五道题放在一起刷其实挺有讲究的。它们恰好覆盖了二叉树最核心的几种遍历方式前序、中序、后序属于深度优先搜索DFS的范畴层序属于广度优先搜索BFS的范畴而最小深度这道题表面上考查的是树的深度计算实际上把DFS和BFS两条路线都串起来了。可以说二叉树遍历的递归模板、迭代栈写法、队列层序遍历技巧以及边界条件判断全都浓缩在这五道题里。这篇文章我从头到尾把这五道题串一遍不讲虚的直接给代码、给执行过程、给踩坑点。不管你用的是C、Java还是Python思路是通用的。写完之后你会发现二叉树的遍历根本不是靠背模板而是靠理解“节点访问时机”和“栈/队列的入出顺序”。1.1 前序、中序、后序命名规则已经告诉你全部信息先看最基础的定义。二叉树的前序、中序、后序遍历三个名字里的“前”“中”“后”指的是根节点被访问的位置前序遍历根节点 → 左子树 → 右子树根在前中序遍历左子树 → 根节点 → 右子树根在中间后序遍历左子树 → 右子树 → 根节点根在后这三个顺序是对“根节点”而言的。左子树永远在右子树之前这一点不变。所以记的时候不需要死记“前中后”只需要记住根在哪前序先输出根再递归左再递归右。中序先递归左再输出根再递归右。后序先递归左再递归右最后输出根。一句话总结根的位置决定了遍历的名字。你只要把根放到对应位置整棵树的输出顺序就对了。1.2 层序和最小深度从“纵向”到“横向”的思路切换层序遍历Level Order Traversal是另一种维度的遍历。DFS系列是一路走到叶子再返回BFS层序遍历则是从上到下、从左到右一层一层地扫过去。比如这样一棵树3 / \ 9 20 / \ 15 7前序输出是 3, 9, 20, 15, 7层序输出是 [3], [9, 20], [15, 7]每一层单独成一组。这个“按层分组”的特性是第102题的关键。第111题最小深度属于“二叉树深度/高度”这类问题。套路上可以递归来做也可以配合层序BFS来做而且BFS在这道题上有天然的效率优势——因为BFS一旦碰到第一个叶子节点就能立刻返回当前层数。这个优化在面试里聊起来很加分。2. 递归解法三行代码解决前中后序递归是二叉树的“母语”。因为二叉树本身就是递归定义的左子树是一棵树右子树也是一棵树。所以用递归去遍历二叉树逻辑最直观代码也最短。2.1 递归三要素终止条件、递归调用、操作时机写二叉树的递归其实只需要记住一个模板void traverse(TreeNode* root) { // 终止条件 if (root nullptr) return; // 前序位置先访问根 traverse(root-left); // 中序位置左子树遍历完访问根 traverse(root-right); // 后序位置左右子树都遍历完访问根 }你发现没有前序、中序、后序的代码结构完全一样区别仅仅在于“操作根节点”的语句放在哪个位置。放在最前面就是前序放在中间就是中序放在最后面就是后序。这就是“访问时机”的核心意义。很多初学者写递归会卡在“为什么这个递归过程和我手动模拟的不一样”。原因在于递归是借助系统调用栈完成的。你调用 traverse(root-left) 的时候当前函数的状态会被压栈保存等左子树全部执行完栈顶弹出回到当前节点继续往下走。理解这一点后面看迭代法就轻松了。2.2 完整代码实现与执行轨迹第144题前序遍历C写法void preorder(TreeNode* root, vectorint res) { if (!root) return; res.push_back(root-val); // 前序先访问根 preorder(root-left, res); // 再左 preorder(root-right, res); // 后右 } vectorint preorderTraversal(TreeNode* root) { vectorint res; preorder(root, res); return res; }第94题中序遍历void inorder(TreeNode* root, vectorint res) { if (!root) return; inorder(root-left, res); // 先左 res.push_back(root-val); // 中序再访问根 inorder(root-right, res); // 后右 } vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root, res); return res; }第145题后序遍历void postorder(TreeNode* root, vectorint res) { if (!root) return; postorder(root-left, res); // 先左 postorder(root-right, res); // 再右 res.push_back(root-val); // 后序最后访问根 } vectorint postorderTraversal(TreeNode* root) { vectorint res; postorder(root, res); return res; }用一棵小树手动走一遍前序遍历root 1左子节点 2右子节点 3其中 2 没有子节点3 的左子节点 4。1 / \ 2 3 / 4前序遍历的执行过程是访问 1 → 进入 2访问 2→ 2 的左右为空返回 → 进入 3访问 3→ 进入 4访问 4→ 4 返回 → 3 返回 → 结束。输出1, 2, 3, 4。中序则是进入 2左空访问 2→ 返回 → 访问 1 → 进入 3 → 进入 4访问 4→ 返回 → 访问 3 → 输出2, 1, 4, 3。后序输出2, 4, 3, 1。2.3 递归解法的局限不仅栈溢出还有效率问题递归虽然好写但有两个问题。第一个是树深度很大时系统栈可能溢出。LeetCode上虽然一般不会让递归爆栈但面试官一定会问“递归的缺点是什么”提前想好这一点非常有价值。第二个问题是递归过程中有大量函数调用开销。这个在LeetCode的测试数据里体现不出来但在真实业务场景中如果一棵树有几万甚至几十万个节点递归的性能瓶颈就出来了。所以掌握迭代法是必须的这不只是面试题也是实操中构建健壮代码的能力。3. 迭代解法用显式栈还原递归过程迭代法的思路是用一个显式栈std::stack来模拟递归调用时的系统栈。理解了递归的执行顺序再来看迭代法你会发现整个过程就是“把递归调用栈手动写出来”。3.1 前序遍历根先出先压右再压左前序的顺序是“根 → 左 → 右”。用栈实现时因为栈是后进先出所以入栈时要先压右子节点再压左子节点这样左子节点才会先被弹出。vectorint preorderTraversal(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return res; }这个思路一句话概括弹一个访问一个把右左依次入栈。很多人写错的地方是入栈顺序记反了就变成“根右左”了。3.2 中序遍历一路向左弹出访问转右继续中序比前序稍微复杂一点因为顺序是“左 → 根 → 右”你不能一开始就把根弹出去访问需要先一路向左压栈直到左子树为空再弹出访问然后转向右子树。vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { // 一路向左压栈 while (cur) { st.push(cur); cur cur-left; } // 弹出访问 cur st.top(); st.pop(); res.push_back(cur-val); // 转向右子树 cur cur-right; } return res; }这里最关键的变量是cur它代表“当前需要处理的节点”。第一个内层 while 把左链全部压栈然后弹出一个访问再让cur指向右子树。右子树同样会进入内层 while 把它的左链压栈。这个过程完整模拟了递归中“进入左子树 → 访问根 → 进入右子树”的步骤。3.3 后序遍历两个栈的思路或者一个栈加反转后序的顺序是“左 → 右 → 根”。直接用一个栈模拟会遇到一个问题根节点被弹出来时还不到访问时机因为要等右子树处理完才能访问。所以后序的迭代实现是三种遍历里最容易出错的。一个经典的技巧是用类似前序的思路先得到“根 → 右 → 左”的顺序然后反转。vectorint postorderTraversal(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); // 注意先压左再压右这样先弹出的是右 if (node-left) st.push(node-left); if (node-right) st.push(node-right); } reverse(res.begin(), res.end()); return res; }这段代码的逻辑是前序版本是“根 → 左 → 右”这里把压栈顺序反过来先压左再压右弹出的顺序就变成了“根 → 右 → 左”。最后整体反转得到“左 → 右 → 根”也就是后序。注意最后一步 reverse 是 O(n) 时间整体时间复杂度仍然是 O(n)空间复杂度 O(n)没毛病。3.4 三种迭代对比什么时候该用哪种写法遍历方式核心思路入栈/处理顺序易错点前序弹一个访问一个右左入栈右 → 左入栈顺序写反中序一路向左压栈弹访问转右左链路压栈忘记 cur cur-right后序前序变体 反转左 → 右 入栈反转结果压栈顺序和前序相反实际上中序和后续的迭代写法还有更“统一”的版本比如给栈里压入带标记的节点visited1表示该访问了这里就不展开——如果面试官要求不用反转写出后序可以用一个prev指针记录上一个访问的节点或者用双栈法。不过个人经验是后序的反转法是最不容易写错的面试时优先保证正确性。4. 第102题层序遍历BFS队列的标准用法层序遍历和前中后序不是一类问题它走的是广度优先借用队列一层一层往外扫。4.1 基础BFS模板队列 循环大多数人的第一版层序代码长这样vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; // 处理当前层 for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; }这里最关键的一行是int size q.size()。它必须在 for 循环之前取因为队列在循环过程中会不断加入下一层的节点q.size()会变化。提前取好sizefor 循环只处理当前层已有的节点下一层的节点自然留在队列里为下一轮外层循环做准备。4.2 为什么要按层分组从一维输出到二维输出第102题要求的输出是一个二维数组每个子数组是某一层的节点。所以你会看到代码里多了一个vectorint level每一层单独收集再 push 到结果。如果换成蛇形走位Z字形输出只需要加一个层号判断偶数层从左到右奇数层从右到左翻转一下level即可。这道题还有个常见的变体是“二叉树的右视图”。思路也是层序只是每层只取最后一个节点。理解了按层分组的模板这些变体基本是半小时内能拿下的量。4.3 层序变体一网打尽二叉树的层序遍历 II自底向上BFS 结束后 reverse 整个res。二叉树的锯齿形层序遍历根据层号奇偶决定是否反转level。二叉树的右视图每层取level.back()。填充每个节点的下一个右侧节点指针层序遍历时用前一个节点pre-next cur。这些都建立在同一个 BFS 模板上。所以第102题不只是背模板理解“当前层节点数量在进入循环前锁定”这个思想后面的变体题都能换汤不换药地解决。5. 第111题最小深度DFS与BFS的抉择第111题要求返回二叉树的最小深度这里的深度是指从根节点到最近叶子节点的最短路径上的节点数。注意几个关键字叶子节点、最近、节点数。这三者缺一不可。5.1 递归写法最容易忽略的“单子树为空”场景最小深度的递归直觉写法是左子树最小深度和右子树最小深度取较小值再加1。对应代码int minDepth(TreeNode* root) { if (!root) return 0; int left minDepth(root-left); int right minDepth(root-right); return min(left, right) 1; }看起来没问题但跑测试就会发现对于一个只有左子树的节点上面代码会返回 1——这是错的。比如下面这棵树1 / 2根节点 1 没有右子树所以right 0min(1, 0) 1 1。但根节点 1 不是叶子节点所以最小深度不可能是 1应该是 2。原因在于当一个节点只有左子树或只有右子树时空的那一侧不能参与最小深度比较。正确写法int minDepth(TreeNode* root) { if (!root) return 0; if (!root-left) return minDepth(root-right) 1; if (!root-right) return minDepth(root-left) 1; return min(minDepth(root-left), minDepth(root-right)) 1; }这算是题意理解的一个小坑但实际面试中问“最小深度”十有八九会碰到这个陷阱。关键判断依据是空节点不算叶子所以不存在“空子树深度为0参与比较”这回事。5.2 BFS解法找到第一个叶子节点就返回BFS 解法与上述 DFS 的递归写法思路不同层序遍历从上到下扫当碰到第一个“左右子节点都为空”的节点时当前层数就是最小深度。由于 BFS 是一层一层扫的第一次遇到叶子节点一定是在最小深度那一层。int minDepth(TreeNode* root) { if (!root) return 0; queuepairTreeNode*, int q; q.push({root, 1}); while (!q.empty()) { auto [node, depth] q.front(); q.pop(); if (!node-left !node-right) return depth; if (node-left) q.push({node-left, depth 1}); if (node-right) q.push({node-right, depth 1}); } return 0; }也可以沿用层序模板用level记录当前层数。BFS 的优点在这个问题里非常明显一旦找到叶子节点就立刻返回不需要遍历整棵树。对于一棵很“偏”的树最坏情况是 BFS 退化成遍历整棵树复杂度仍是 O(n)但平均情况下 BFS 往往比 DFS 更早返回。5.3 最大深度 vs 最小深度一个容易混淆的点最大深度用 DFS 递归写起来就简单得多不会有人写错max(left, right) 1。最大和最小的区别在于最大深度可以用空子树返回 0 来参与比较因为max(0, 1) 1不影响正确性最小深度则不行因为min(0, 1) 0会直接吞掉另一侧的实际深度。理解了这个逻辑你就能从“背题”升级到“懂题”。6. 实战中的边界条件与常见坑位五道题刷一遍容易但会犯的错基本都集中在边界条件上。这里我按踩坑频率从高到低列一遍都是真实刷题和面试中见过的问题。6.1 空树任何遍历的第一步都是判空几乎每一道二叉树题目的递归版本开头都是if (!root) return ...。迭代版本则要在开始时就判断if (!root) return ...否则访问root-val直接空指针异常。尤其是在层序和最小深度题里空树返回的应该是空数组或 0千万别把空指针推进队列。6.2 队列和栈里存的是什么节点本身还是包装对象层序遍历 BFS 的队列queueTreeNode*存的是节点指针第111题的最小深度 BFS 版本存的是pairTreeNode*, int用来同时记录节点和层数。有些同学图省事只存int depth那你就丢失了节点信息根本没法继续遍历。分清容器里存的东西是你代码能否跑通的关键。实际上还有一种更巧的写法是每层用一个for循环depth在外层循环中加1队列只存节点。这种写法在代码上更统一。6.3 递归和迭代的时间/空间复杂度解法时间复杂度空间复杂度递归调用栈/栈/队列递归 DFSO(n)O(h)h 为树高迭代 DFSO(n)O(h)层序 BFSO(n)O(n)最坏情况是一层能放 n/2 个节点在 LeetCode 的题解讨论区很多人只关注时间复杂度是 O(n)但空间复杂度的分析一样是面试必问。递归的空间复杂度是调用栈的深度也就是树的高度如果树退化成链表h n就会 O(n) 空间。6.4 调试技巧如何用一个小输入验证代码二叉树的题目调试有一个非常高效的方法用最小测试用例逐步走查。比如用一个只有根节点的树、一个只有左子树的树、一个空树分别跑一遍前中后序、层序、最小深度。这三个用例能挡住 90% 的边界错误。另外写代码前先自己在纸上把树画出来标出预期遍历顺序再跑代码对照。我见过太多同学上来就刷题连前序和后序输出到底差在哪都没想清楚代码写错了也不知道。如果面试时被要求“手动模拟一遍算法流程”画图 口头模拟的能力比代码本身更让面试官眼前一亮。7. 从五道题到一套通用方法论五道题刷完回头看它们其实在锻炼同一套能力你把一棵树抽象成一个数据流然后用某种方式把数据流里的元素拿出来。7.1 判空、递归、栈模拟、队列模拟套路万变不离其宗递归解法依赖系统栈迭代解法依赖显式栈。DFS前中后序的本质是“先深入再回溯”用栈或递归实现。BFS层序的本质是“逐层扩散”用队列实现。最小深度的 DFS 版本要处理单子树为空BFS 版本则找到叶子即返回。这套方法论不只能解决二叉树题。当你去做图的遍历、拓扑排序、最短路径时DFS 和 BFS 的框架照样适用。说白了二叉树只是练习 DFS/BFS 最好的“试验田”因为它的递归结构足够简单不会让初学者在复杂图结构上迷失。7.2 后续扩展从这五道题出发能通向哪里二叉树的题目在 LeetCode 上是绝对的大类。刷完这五道题你可以按这个路径继续扩展路径和系列从根到叶的路径和、路径总和 III用 DFS 的本质去解决。构造二叉树从前序与中序遍历序列构造二叉树、从中序与后序遍历序列构造二叉树正好用上你刚学的遍历知识。二叉搜索树BST 的中序遍历结果是升序序列这个性质能解大量 BST 题目。最近公共祖先递归在后序位置做判断是后续遍历的经典应用。Morris 遍历如果不满足于 O(h) 空间可以把空间复杂度压到 O(1)面试进阶话题。另外我多说一句实际工程里二叉树的遍历也常常出现。比如 JSON 的树形结构处理、文件目录的递归遍历、搜索引擎索引树的遍历、表达式树的计算底层思路都和这五道题相通。嵌入式方向的朋友如果接触过 AVL 树、红黑树也会发现它们的插入、删除操作里大量用到遍历的思路。所以说这五道题看似刷的是“算法基础题”实际上是在打工程能力的地基。最后分享一个我自己的习惯遇到二叉树题目我先不写代码先在白板上画一棵三层的小树把遍历序列手写出来再对着序列写代码。这样代码写完测试用例已经在脑子里跑过一遍了提交通过率会高很多。这个习惯帮我省了大量反复调试的时间也推荐你试试。 二叉树遍历五题串讲：前中后序、层序与最小深度，递归迭代全掌握
1. 先把五行代码的“血缘关系”理清楚刷LeetCode的朋友应该都有过这样一种体验今天刷了144题前序遍历AC了感觉很简单明天做94题中序遍历也AC了觉得不过如此后天碰到145题后序遍历顺手就写完了——然后第102题层序遍历直接懵了第111题最小深度又开始怀疑自己到底懂不懂二叉树。这五道题放在一起刷其实挺有讲究的。它们恰好覆盖了二叉树最核心的几种遍历方式前序、中序、后序属于深度优先搜索DFS的范畴层序属于广度优先搜索BFS的范畴而最小深度这道题表面上考查的是树的深度计算实际上把DFS和BFS两条路线都串起来了。可以说二叉树遍历的递归模板、迭代栈写法、队列层序遍历技巧以及边界条件判断全都浓缩在这五道题里。这篇文章我从头到尾把这五道题串一遍不讲虚的直接给代码、给执行过程、给踩坑点。不管你用的是C、Java还是Python思路是通用的。写完之后你会发现二叉树的遍历根本不是靠背模板而是靠理解“节点访问时机”和“栈/队列的入出顺序”。1.1 前序、中序、后序命名规则已经告诉你全部信息先看最基础的定义。二叉树的前序、中序、后序遍历三个名字里的“前”“中”“后”指的是根节点被访问的位置前序遍历根节点 → 左子树 → 右子树根在前中序遍历左子树 → 根节点 → 右子树根在中间后序遍历左子树 → 右子树 → 根节点根在后这三个顺序是对“根节点”而言的。左子树永远在右子树之前这一点不变。所以记的时候不需要死记“前中后”只需要记住根在哪前序先输出根再递归左再递归右。中序先递归左再输出根再递归右。后序先递归左再递归右最后输出根。一句话总结根的位置决定了遍历的名字。你只要把根放到对应位置整棵树的输出顺序就对了。1.2 层序和最小深度从“纵向”到“横向”的思路切换层序遍历Level Order Traversal是另一种维度的遍历。DFS系列是一路走到叶子再返回BFS层序遍历则是从上到下、从左到右一层一层地扫过去。比如这样一棵树3 / \ 9 20 / \ 15 7前序输出是 3, 9, 20, 15, 7层序输出是 [3], [9, 20], [15, 7]每一层单独成一组。这个“按层分组”的特性是第102题的关键。第111题最小深度属于“二叉树深度/高度”这类问题。套路上可以递归来做也可以配合层序BFS来做而且BFS在这道题上有天然的效率优势——因为BFS一旦碰到第一个叶子节点就能立刻返回当前层数。这个优化在面试里聊起来很加分。2. 递归解法三行代码解决前中后序递归是二叉树的“母语”。因为二叉树本身就是递归定义的左子树是一棵树右子树也是一棵树。所以用递归去遍历二叉树逻辑最直观代码也最短。2.1 递归三要素终止条件、递归调用、操作时机写二叉树的递归其实只需要记住一个模板void traverse(TreeNode* root) { // 终止条件 if (root nullptr) return; // 前序位置先访问根 traverse(root-left); // 中序位置左子树遍历完访问根 traverse(root-right); // 后序位置左右子树都遍历完访问根 }你发现没有前序、中序、后序的代码结构完全一样区别仅仅在于“操作根节点”的语句放在哪个位置。放在最前面就是前序放在中间就是中序放在最后面就是后序。这就是“访问时机”的核心意义。很多初学者写递归会卡在“为什么这个递归过程和我手动模拟的不一样”。原因在于递归是借助系统调用栈完成的。你调用 traverse(root-left) 的时候当前函数的状态会被压栈保存等左子树全部执行完栈顶弹出回到当前节点继续往下走。理解这一点后面看迭代法就轻松了。2.2 完整代码实现与执行轨迹第144题前序遍历C写法void preorder(TreeNode* root, vectorint res) { if (!root) return; res.push_back(root-val); // 前序先访问根 preorder(root-left, res); // 再左 preorder(root-right, res); // 后右 } vectorint preorderTraversal(TreeNode* root) { vectorint res; preorder(root, res); return res; }第94题中序遍历void inorder(TreeNode* root, vectorint res) { if (!root) return; inorder(root-left, res); // 先左 res.push_back(root-val); // 中序再访问根 inorder(root-right, res); // 后右 } vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root, res); return res; }第145题后序遍历void postorder(TreeNode* root, vectorint res) { if (!root) return; postorder(root-left, res); // 先左 postorder(root-right, res); // 再右 res.push_back(root-val); // 后序最后访问根 } vectorint postorderTraversal(TreeNode* root) { vectorint res; postorder(root, res); return res; }用一棵小树手动走一遍前序遍历root 1左子节点 2右子节点 3其中 2 没有子节点3 的左子节点 4。1 / \ 2 3 / 4前序遍历的执行过程是访问 1 → 进入 2访问 2→ 2 的左右为空返回 → 进入 3访问 3→ 进入 4访问 4→ 4 返回 → 3 返回 → 结束。输出1, 2, 3, 4。中序则是进入 2左空访问 2→ 返回 → 访问 1 → 进入 3 → 进入 4访问 4→ 返回 → 访问 3 → 输出2, 1, 4, 3。后序输出2, 4, 3, 1。2.3 递归解法的局限不仅栈溢出还有效率问题递归虽然好写但有两个问题。第一个是树深度很大时系统栈可能溢出。LeetCode上虽然一般不会让递归爆栈但面试官一定会问“递归的缺点是什么”提前想好这一点非常有价值。第二个问题是递归过程中有大量函数调用开销。这个在LeetCode的测试数据里体现不出来但在真实业务场景中如果一棵树有几万甚至几十万个节点递归的性能瓶颈就出来了。所以掌握迭代法是必须的这不只是面试题也是实操中构建健壮代码的能力。3. 迭代解法用显式栈还原递归过程迭代法的思路是用一个显式栈std::stack来模拟递归调用时的系统栈。理解了递归的执行顺序再来看迭代法你会发现整个过程就是“把递归调用栈手动写出来”。3.1 前序遍历根先出先压右再压左前序的顺序是“根 → 左 → 右”。用栈实现时因为栈是后进先出所以入栈时要先压右子节点再压左子节点这样左子节点才会先被弹出。vectorint preorderTraversal(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return res; }这个思路一句话概括弹一个访问一个把右左依次入栈。很多人写错的地方是入栈顺序记反了就变成“根右左”了。3.2 中序遍历一路向左弹出访问转右继续中序比前序稍微复杂一点因为顺序是“左 → 根 → 右”你不能一开始就把根弹出去访问需要先一路向左压栈直到左子树为空再弹出访问然后转向右子树。vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { // 一路向左压栈 while (cur) { st.push(cur); cur cur-left; } // 弹出访问 cur st.top(); st.pop(); res.push_back(cur-val); // 转向右子树 cur cur-right; } return res; }这里最关键的变量是cur它代表“当前需要处理的节点”。第一个内层 while 把左链全部压栈然后弹出一个访问再让cur指向右子树。右子树同样会进入内层 while 把它的左链压栈。这个过程完整模拟了递归中“进入左子树 → 访问根 → 进入右子树”的步骤。3.3 后序遍历两个栈的思路或者一个栈加反转后序的顺序是“左 → 右 → 根”。直接用一个栈模拟会遇到一个问题根节点被弹出来时还不到访问时机因为要等右子树处理完才能访问。所以后序的迭代实现是三种遍历里最容易出错的。一个经典的技巧是用类似前序的思路先得到“根 → 右 → 左”的顺序然后反转。vectorint postorderTraversal(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); // 注意先压左再压右这样先弹出的是右 if (node-left) st.push(node-left); if (node-right) st.push(node-right); } reverse(res.begin(), res.end()); return res; }这段代码的逻辑是前序版本是“根 → 左 → 右”这里把压栈顺序反过来先压左再压右弹出的顺序就变成了“根 → 右 → 左”。最后整体反转得到“左 → 右 → 根”也就是后序。注意最后一步 reverse 是 O(n) 时间整体时间复杂度仍然是 O(n)空间复杂度 O(n)没毛病。3.4 三种迭代对比什么时候该用哪种写法遍历方式核心思路入栈/处理顺序易错点前序弹一个访问一个右左入栈右 → 左入栈顺序写反中序一路向左压栈弹访问转右左链路压栈忘记 cur cur-right后序前序变体 反转左 → 右 入栈反转结果压栈顺序和前序相反实际上中序和后续的迭代写法还有更“统一”的版本比如给栈里压入带标记的节点visited1表示该访问了这里就不展开——如果面试官要求不用反转写出后序可以用一个prev指针记录上一个访问的节点或者用双栈法。不过个人经验是后序的反转法是最不容易写错的面试时优先保证正确性。4. 第102题层序遍历BFS队列的标准用法层序遍历和前中后序不是一类问题它走的是广度优先借用队列一层一层往外扫。4.1 基础BFS模板队列 循环大多数人的第一版层序代码长这样vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; // 处理当前层 for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; }这里最关键的一行是int size q.size()。它必须在 for 循环之前取因为队列在循环过程中会不断加入下一层的节点q.size()会变化。提前取好sizefor 循环只处理当前层已有的节点下一层的节点自然留在队列里为下一轮外层循环做准备。4.2 为什么要按层分组从一维输出到二维输出第102题要求的输出是一个二维数组每个子数组是某一层的节点。所以你会看到代码里多了一个vectorint level每一层单独收集再 push 到结果。如果换成蛇形走位Z字形输出只需要加一个层号判断偶数层从左到右奇数层从右到左翻转一下level即可。这道题还有个常见的变体是“二叉树的右视图”。思路也是层序只是每层只取最后一个节点。理解了按层分组的模板这些变体基本是半小时内能拿下的量。4.3 层序变体一网打尽二叉树的层序遍历 II自底向上BFS 结束后 reverse 整个res。二叉树的锯齿形层序遍历根据层号奇偶决定是否反转level。二叉树的右视图每层取level.back()。填充每个节点的下一个右侧节点指针层序遍历时用前一个节点pre-next cur。这些都建立在同一个 BFS 模板上。所以第102题不只是背模板理解“当前层节点数量在进入循环前锁定”这个思想后面的变体题都能换汤不换药地解决。5. 第111题最小深度DFS与BFS的抉择第111题要求返回二叉树的最小深度这里的深度是指从根节点到最近叶子节点的最短路径上的节点数。注意几个关键字叶子节点、最近、节点数。这三者缺一不可。5.1 递归写法最容易忽略的“单子树为空”场景最小深度的递归直觉写法是左子树最小深度和右子树最小深度取较小值再加1。对应代码int minDepth(TreeNode* root) { if (!root) return 0; int left minDepth(root-left); int right minDepth(root-right); return min(left, right) 1; }看起来没问题但跑测试就会发现对于一个只有左子树的节点上面代码会返回 1——这是错的。比如下面这棵树1 / 2根节点 1 没有右子树所以right 0min(1, 0) 1 1。但根节点 1 不是叶子节点所以最小深度不可能是 1应该是 2。原因在于当一个节点只有左子树或只有右子树时空的那一侧不能参与最小深度比较。正确写法int minDepth(TreeNode* root) { if (!root) return 0; if (!root-left) return minDepth(root-right) 1; if (!root-right) return minDepth(root-left) 1; return min(minDepth(root-left), minDepth(root-right)) 1; }这算是题意理解的一个小坑但实际面试中问“最小深度”十有八九会碰到这个陷阱。关键判断依据是空节点不算叶子所以不存在“空子树深度为0参与比较”这回事。5.2 BFS解法找到第一个叶子节点就返回BFS 解法与上述 DFS 的递归写法思路不同层序遍历从上到下扫当碰到第一个“左右子节点都为空”的节点时当前层数就是最小深度。由于 BFS 是一层一层扫的第一次遇到叶子节点一定是在最小深度那一层。int minDepth(TreeNode* root) { if (!root) return 0; queuepairTreeNode*, int q; q.push({root, 1}); while (!q.empty()) { auto [node, depth] q.front(); q.pop(); if (!node-left !node-right) return depth; if (node-left) q.push({node-left, depth 1}); if (node-right) q.push({node-right, depth 1}); } return 0; }也可以沿用层序模板用level记录当前层数。BFS 的优点在这个问题里非常明显一旦找到叶子节点就立刻返回不需要遍历整棵树。对于一棵很“偏”的树最坏情况是 BFS 退化成遍历整棵树复杂度仍是 O(n)但平均情况下 BFS 往往比 DFS 更早返回。5.3 最大深度 vs 最小深度一个容易混淆的点最大深度用 DFS 递归写起来就简单得多不会有人写错max(left, right) 1。最大和最小的区别在于最大深度可以用空子树返回 0 来参与比较因为max(0, 1) 1不影响正确性最小深度则不行因为min(0, 1) 0会直接吞掉另一侧的实际深度。理解了这个逻辑你就能从“背题”升级到“懂题”。6. 实战中的边界条件与常见坑位五道题刷一遍容易但会犯的错基本都集中在边界条件上。这里我按踩坑频率从高到低列一遍都是真实刷题和面试中见过的问题。6.1 空树任何遍历的第一步都是判空几乎每一道二叉树题目的递归版本开头都是if (!root) return ...。迭代版本则要在开始时就判断if (!root) return ...否则访问root-val直接空指针异常。尤其是在层序和最小深度题里空树返回的应该是空数组或 0千万别把空指针推进队列。6.2 队列和栈里存的是什么节点本身还是包装对象层序遍历 BFS 的队列queueTreeNode*存的是节点指针第111题的最小深度 BFS 版本存的是pairTreeNode*, int用来同时记录节点和层数。有些同学图省事只存int depth那你就丢失了节点信息根本没法继续遍历。分清容器里存的东西是你代码能否跑通的关键。实际上还有一种更巧的写法是每层用一个for循环depth在外层循环中加1队列只存节点。这种写法在代码上更统一。6.3 递归和迭代的时间/空间复杂度解法时间复杂度空间复杂度递归调用栈/栈/队列递归 DFSO(n)O(h)h 为树高迭代 DFSO(n)O(h)层序 BFSO(n)O(n)最坏情况是一层能放 n/2 个节点在 LeetCode 的题解讨论区很多人只关注时间复杂度是 O(n)但空间复杂度的分析一样是面试必问。递归的空间复杂度是调用栈的深度也就是树的高度如果树退化成链表h n就会 O(n) 空间。6.4 调试技巧如何用一个小输入验证代码二叉树的题目调试有一个非常高效的方法用最小测试用例逐步走查。比如用一个只有根节点的树、一个只有左子树的树、一个空树分别跑一遍前中后序、层序、最小深度。这三个用例能挡住 90% 的边界错误。另外写代码前先自己在纸上把树画出来标出预期遍历顺序再跑代码对照。我见过太多同学上来就刷题连前序和后序输出到底差在哪都没想清楚代码写错了也不知道。如果面试时被要求“手动模拟一遍算法流程”画图 口头模拟的能力比代码本身更让面试官眼前一亮。7. 从五道题到一套通用方法论五道题刷完回头看它们其实在锻炼同一套能力你把一棵树抽象成一个数据流然后用某种方式把数据流里的元素拿出来。7.1 判空、递归、栈模拟、队列模拟套路万变不离其宗递归解法依赖系统栈迭代解法依赖显式栈。DFS前中后序的本质是“先深入再回溯”用栈或递归实现。BFS层序的本质是“逐层扩散”用队列实现。最小深度的 DFS 版本要处理单子树为空BFS 版本则找到叶子即返回。这套方法论不只能解决二叉树题。当你去做图的遍历、拓扑排序、最短路径时DFS 和 BFS 的框架照样适用。说白了二叉树只是练习 DFS/BFS 最好的“试验田”因为它的递归结构足够简单不会让初学者在复杂图结构上迷失。7.2 后续扩展从这五道题出发能通向哪里二叉树的题目在 LeetCode 上是绝对的大类。刷完这五道题你可以按这个路径继续扩展路径和系列从根到叶的路径和、路径总和 III用 DFS 的本质去解决。构造二叉树从前序与中序遍历序列构造二叉树、从中序与后序遍历序列构造二叉树正好用上你刚学的遍历知识。二叉搜索树BST 的中序遍历结果是升序序列这个性质能解大量 BST 题目。最近公共祖先递归在后序位置做判断是后续遍历的经典应用。Morris 遍历如果不满足于 O(h) 空间可以把空间复杂度压到 O(1)面试进阶话题。另外我多说一句实际工程里二叉树的遍历也常常出现。比如 JSON 的树形结构处理、文件目录的递归遍历、搜索引擎索引树的遍历、表达式树的计算底层思路都和这五道题相通。嵌入式方向的朋友如果接触过 AVL 树、红黑树也会发现它们的插入、删除操作里大量用到遍历的思路。所以说这五道题看似刷的是“算法基础题”实际上是在打工程能力的地基。最后分享一个我自己的习惯遇到二叉树题目我先不写代码先在白板上画一棵三层的小树把遍历序列手写出来再对着序列写代码。这样代码写完测试用例已经在脑子里跑过一遍了提交通过率会高很多。这个习惯帮我省了大量反复调试的时间也推荐你试试。