二叉树递归遍历经典题型实战：翻转、对称与深度全解析

1. 二叉树专题2整体定位：遍历模板与实战应用的分水岭

1.1 从“会遍历”到“会解题”，思维怎么升级

训练营打卡到第14天，二叉树专题2迎面而来。说实话，专题1结束的时候我还有点飘，前中后序遍历的递归模板背得滚瓜烂熟，层序模板也写得飞快，以为自己已经拿捏二叉树了。结果专题2的第一道题翻转二叉树就给我上了一课：模板会背只是起点，能不能在遍历的过程中做文章，才是真正拉开差距的地方。

专题1的核心是“怎么走”，专题2的核心是“走的时候顺便干什么”。同样是一棵二叉树，同样要从根走到叶子，但每道题要在不同的时机处理节点，返回不同的值，甚至要同时遍历两棵树。这个思维跃迁如果不做好铺垫，很容易出现一种情况：看题解觉得很简单，自己一写就各种报错，或者答案不对。

我个人理解，专题2本质上是在回答三个问题：递归函数到底要返回什么、什么时候处理当前节点、左右子树的结果怎么被当前节点使用。这三个问题想通了，后面无论刷多少二叉树题目，基本都是套同一个框架。

1.2 这一专题的经典题型与递进关系

围绕二叉树专题2，常见的核心题目大致有这些：

• 翻转二叉树
• 对称二叉树
• 二叉树的最大深度
• 二叉树的最小深度
• 完全二叉树的节点个数
• 二叉树的所有路径

有些版本还会把平衡二叉树、左叶子之和也放进这个专题，但不管版本怎么变，上面六道题几乎必刷。这些题目的递进关系非常明显：翻转二叉树是单棵树的遍历中执行交换操作，对称二叉树升级成两棵树同时比较，最大深度开始让递归返回一个数值，最小深度则在这个数值上增加了边界条件的坑，节点个数又进一步结合完全二叉树的性质做剪枝，最后路径问题引入回溯。每一道新题都在前一道题的基础上加一点点复杂度，这种坡度对新手非常友好。

如果打乱顺序刷，效果就差很多。比如直接做路径问题，你既要处理递归又要处理回溯，可能还要调试字符串拼接，多个难点混在一起很容易心态崩。所以这类训练营把题目排成专题2的固定顺序，是有道理的。

1.3 为什么顺序很重要：以一个三节点小树为例

拿一棵最简单的小树来演示：根节点是1，左孩子是2，右孩子是3。注意，这里孩子节点都没有子树，所以“叶子”就是2和3。

如果题目是翻转二叉树，遍历到根节点1的时候，就应该立刻交换左右孩子，然后再去处理2和3。如果先递归处理左右子树，后交换，也能得到正确结果。这里前序和后序都能用，但中序就特别容易出问题，因为中序访问完左子树之后，交换左右孩子，再访问“右子树”时，实际访问的可能是原来的左子树，逻辑会变得很绕。

如果题目是求最大深度，那就必须先知道2和3各自的深度分别是1，然后在根节点返回1 + max(1,1) = 2。这种情况下，你只能在处理完左右子树之后再去“汇总”，也就是后序。

同样是遍历，操作时机不同，最终结果就不同。用三节点小树在纸上模拟一遍，基本就能理解为什么有的题用前序、有的题用后序。这个认知比背任何模板都重要。

2. 核心细节解析：递归三要素与遍历顺序的选择

2.1 递归函数设计的三个决定

写递归题的时候，我习惯在动代码前先回答三个问题：

第一个问题：这个递归函数返回什么？是返回处理后的新指针、一个布尔值，还是一个整数深度？这个决定直接影响了函数的签名和每一层递归的写法。翻转二叉树返回TreeNode*，对称二叉树返回bool，最大深度返回int。不要小看这一步，很多人写着写着就把返回值类型搞混，然后整个递归链路对不上。

第二个问题：终止条件是什么？二叉树递归最常见的终止条件是节点为空。但空节点应该返回什么，需要根据题目语义决定。求最大深度时，空节点返回0；对称比较时，两个空节点返回true，一个空节点返回false；翻转二叉树时，空节点直接返回nullptr。这些都是不同的语义，不能统一套用。

第三个问题：单层递归的逻辑是什么？先处理当前节点，还是先递归孩子？这决定了遍历顺序。翻转二叉树先交换当前节点的左右孩子，然后递归下去；最大深度必须先递归得到左右子树高度，再返回当前高度。顺序是由题目需求决定的，不是随心所欲。

想清楚这三个问题后，剩下的就是“信任递归函数”。这句话很多人听不进去，但它是递归能写对的关键。当你调用 invertTree(root->right) 的时候，不要试图在脑海里展开它内部所有步骤，你要相信它一定会返回“翻转好的右子树”。只要函数签名、终止条件、单层逻辑三者一致，递归的运行结果就是确定的。每一次尝试手动模拟递归的每一步，都会让你更容易写出错误。

2.2 前序、中序、后序到底怎么选

这个问题在专题2里被反复问到。我的经验是：不要背“哪道题用哪个顺序”，而是看数据流向。

如果当前节点的结果依赖左右子树的结果，比如最大深度、节点个数，那一定是后序。为什么？因为你要先拿到左右孩子的结果，才能计算当前节点。这个数据流是自底向上的，对应后序。

如果当前节点的操作不依赖子树结果，只要在遍历时顺手改一改，比如翻转二叉树，那前序、后序、层序都可以，中序需要额外小心。对称二叉树稍微特殊，它虽然看上去是前序式的中-左-右比较，但实际需要把左右孩子的比较结果收集上来，用&&合并，所以从数据流上看更接近后序。

为了加深理解，可以把数据流想象成“上楼梯”。你需要先知道下面两层的信息，才能在上一层得出结论，这就是后序；如果只需要在每一层做固定动作，不管下面多深，每层做完就往下一层走，那就是前序。

判断标准就这么简单：先处理当前节点能得到结果，还是先处理孩子能得到结果？前者用前序，后者用后序。多画几次递归树，这个判断就会成为本能。

2.3 递归深度与迭代法兜底

递归写起来简单，但不是没有代价。如果二叉树退化成一个链状的“之”字形，递归深度可能达到 n，也就是节点个数。大多数编程语言对递归深度都有限制，比如默认栈空间不够时，深度过万就可能栈溢出。面试或提交在线评测时，偶尔会遇到专门构造链状树的极端用例。

所以专题2里的题目，最好每次都用递归先写出正确解，再想一想迭代版本怎么写。翻转二叉树用层序遍历加队列就能改；最大深度用层序遍历数层数；对称二叉树用队列成对入队比较；最小深度甚至可以遇到第一个叶子就返回层数，反而比递归更直观。

迭代和递归不是二选一。掌握两种写法，一是为了应对面试官追问，二是能帮你更清楚地理解递归的本质。我写迭代版的时候，经常发现原来某个递归隐藏式地依赖了函数调用栈，这本身就是很好的学习线索。

3. 实操过程与核心环节实现：经典题一步步写下来

3.1 翻转二叉树：在遍历中完成左右交换

翻转二叉树的要求非常直白：每个节点的左右孩子都交换。递归解法可以说是二叉树递归题的“Hello World”。

先按三要素来：返回值是处理后的根节点，直接返回TreeNode*；终止条件是空节点；单层逻辑是交换左右孩子，然后递归两边。

C++代码长这样：

TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return nullptr; swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root; }

很多初学者会纠结：先swap还是先递归？上面代码是先swap，再递归。其实对于翻转二叉树，前序和后序都能通过，关键是不要用中序。中序版本可能写成这样：

TreeNode* invertTree(TreeNode* root) { if (!root) return nullptr; invertTree(root->left); swap(root->left, root->right); invertTree(root->left); return root; }

这段代码看起来诡异，实际上经过第一次递归和交换之后，原来右子树被换到了左边，原左子树被换到了右边。第二次递归访问 root->left 时，处理的其实是最初的右子树。从结果看它也能翻转成功，但推导过程非常绕，一不留神就在换之后写出了错误的递归目标。不推荐在面试时展示这种写法。

迭代层序版本也很简单，核心思想是“每个节点出队时交换左右孩子”：

TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return nullptr; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); swap(node->left, node->right); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } return root; }

这个题目最大的价值在于让你意识到：所谓“某种具体操作”，只要是在遍历每个节点时执行，理论上所有遍历方式都能完成。真正的难点不是交换动作，而是你对遍历顺序的理解。

3.2 对称二叉树：同时遍历两棵子树的镜像分支

对称二叉树要求判断一棵树是否镜像对称。这个题不像翻转二叉树只需要在一棵树上操作，它要求你同时比较两棵树：根节点的左子树和右子树。

递归比较函数接收两个节点，一个来自左子树，一个来自右子树。三个终止条件需要一次性想清楚：

• 两个节点都为空：对称，返回true。
• 一个为空另一个不为空：不对称，返回false。
• 两个不为空但值不相同：不对称，返回false。

除此之外，还要继续比较镜像位置：left->left 和 right->right、left->right 和 right->left。两个结果必须同时为true，所以用 && 连接。

C++代码：

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; if (left == nullptr || right == nullptr) return false; if (left->val != right->val) return false; return compare(left->left, right->right) && compare(left->right, right->left); }

这里的核心细节在于：不要试图用单棵树的结构去套。你是在比较两棵子树，所以递归函数必须接收两个参数。这是“双树同时遍历”的典型题，也是后面很多题目（比如合并二叉树）的基础。

如果你想用迭代版本，可以维护一个队列，每次弹出两个节点比较，再按照镜像关系成对入队。入队顺序必须是 left->left、right->right 一组，left->right、right->left 一组，串了就没意义了。

3.3 最大深度与最小深度：后序遍历的典型应用

最大深度定义是根节点到最远叶子节点的节点数。递归思路是：分别求左右子树的最大深度，取较大者再加1。这是自底向上收集信息的经典模型。

int maxDepth(TreeNode* root) { if (root == nullptr) return 0; int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return 1 + max(leftDepth, rightDepth); }

这段代码非常简洁，但如果只看不写，很容易忽略它为什么是后序。注意 leftDepth 和 rightDepth 必须先递归计算出来，然后当前节点才返回结果。这本质上就是“子树结果汇总到父节点”。

最小深度就没这么简单了。最小深度是根节点到最近叶子节点的节点数。很多人第一反应把 max 换成 min：

int minDepth(TreeNode* root) { if (!root) return 0; return 1 + min(minDepth(root->left), minDepth(root->right)); }

这段代码是错的。考虑一棵只有右子树的链状树：根节点的左孩子为空，右孩子一路延伸。按上面的写法，左子树返回0，右子树返回正确深度，min(0, depth) 恒为0，最后结果变成1，但正确答案是右子树的深度加1。因为空节点并不代表叶子路径，一边为空时，有效深度在另一边。

正确的递归要判断左右孩子是否为空：

int minDepth(TreeNode* root) { if (root == nullptr) return 0; int leftDepth = minDepth(root->left); int rightDepth = minDepth(root->right); if (root->left == nullptr && root->right != nullptr) { return 1 + rightDepth; } if (root->left != nullptr && root->right == nullptr) { return 1 + leftDepth; } return 1 + min(leftDepth, rightDepth); }

我实际刷题时，第一次就栽在这个坑里。后来我把最小深度这个题也写过层序版本：层序一层层往下走，遇到第一个左右孩子都为空的节点直接返回当前层数。这种解法更符合“最近叶子”的直觉，也能绕开空节点分叉的问题。

3.4 完全二叉树的节点个数：普通做法与性质剪枝

如果只是求节点个数，递归起来毫无压力：

int countNodes(TreeNode* root) { if (root == nullptr) return 0; return 1 + countNodes(root->left) + countNodes(root->right); }

这个写法的时间复杂度是 O(n)。但如果题目明确说是完全二叉树，你还能利用它的性质做优化：完全二叉树的某个子树如果是满二叉树，节点数可以直接按公式算，不需要再往下递归。

怎么判断一棵子树是不是满二叉树？很简单：从它的左孩子开始一路往左走到底得到的深度，和从右孩子一路往右走到底得到的深度相等。如果相等，说明左右边界在同一个深度上，这棵子树是满的；如果不相等，就继续递归分裂。

C++代码：

int countNodes(TreeNode* root) { if (root == nullptr) return 0; int leftDepth = 0, rightDepth = 0; TreeNode* left = root->left; TreeNode* right = root->right; while (left) { leftDepth++; left = left->left; } while (right) { rightDepth++; right = right->right; } if (leftDepth == rightDepth) { return (2 << leftDepth) - 1; } return 1 + countNodes(root->left) + countNodes(root->right); }

注意这里的 leftDepth 和 rightDepth 是从当前节点的左右孩子开始数的边数，不是从当前节点本身数。所以满二叉树节点数公式是 2^(leftDepth+1) - 1，代码写成(2 << leftDepth) - 1。如果 leftDepth = 0，2 << 0等于2，2-1等于1，正好只有一个节点，这是对的。

这个优化能把时间从 O(n) 降到 O(log n * log n)。虽然日常刷题不一定必须做到这一步，但面试官问到“有没有更高效的做法”时，能流利讲出这个思路，印象分明显不一样。

3.5 二叉树的所有路径：回溯是路径记录的灵魂

路径问题在专题2里算是一个小高潮。题目要求输出所有从根节点到叶子节点的路径，比如1->2->5这样的字符串。

递归采用前序遍历思路：先把当前节点值加入路径，如果当前节点是叶子，就把整个路径转换成字符串放入结果；如果不是叶子，递归处理左孩子和右孩子。但这里有一个关键动作：递归返回之后，要把刚刚加入的节点从路径中弹出，这就是回溯。

C++代码：

vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if (root) traversal(root, path, result); return result; } void traversal(TreeNode* node, vector<int>& path, vector<string>& result) { path.push_back(node->val); if (node->left == nullptr && node->right == nullptr) { string s; for (int i = 0; i < path.size(); i++) { if (i > 0) s += "->"; s += to_string(path[i]); } result.push_back(s); return; } if (node->left) { traversal(node->left, path, result); path.pop_back(); } if (node->right) { traversal(node->right, path, result); path.pop_back(); } }

为什么必须 pop_back？因为 path 在所有递归层之间共享。处理完左子树回到当前节点后，如果不把左子树的节点弹出，接下来遍历右子树时，右子树的路径前面就会残留左子树的内容。这是回溯思想在二叉树上的第一次正式登场。

如果忘记回溯，常见的报错场景是：输出结果里出现了1->2->5->3这种路径，一看就知道右子树路径错误地拼上了左子树遗留的节点。排查这类问题，就是在每个叶子节点打印当前 path 的全部内容，问题立刻暴露。

4. 常见问题与排查技巧实录：那些年我们一起踩过的坑

4.1 递归返回值没接住，对称判断漏分支

对称二叉树最常见的错误是递归返回条件写得过于随意。有人会写成：

if (left->val == right->val) return compare(left->left, right->right);

少了另一个镜像分支，等于只检查了部分对称路径。因为一棵树要满足对称，必须同时满足内外侧都相等，这个“同时”必须用 && 来保证。如果只检查一侧，遇到这样的情况就会漏判：左子树的左分支能对上右子树的右分支，但左子树的右分支对不上右子树的左分支，整体不对称，代码却返回true。

排查方式是打印 compare 的输入节点值，看递归到了哪一层开始不对称。只要打印信息足够细，很快能找到漏掉的分支。

4.2 最小深度直接取 min，链状树翻车

最小深度这个题的错误率很高。一半人写成直接用 min，另一半人虽然写了判断，但判断条件写反，导致空子树分支返回了错误深度。

前面已经演示过正确写法，这里补充一个更工程化的视角：最小深度定义依赖叶子节点，所以递归里要先看当前节点是否是叶子。一个很好的处理是：如果左右孩子都空，返回1；如果左空右不空，递归右子树；如果右空左不空，递归左子树；否则取两边最小值加1。这个写法把所有分支情况都显式列出来，虽然啰嗦，但不容易出错。

层序迭代版本也很适合作为答案兜底。只要按层遍历，记录层数，碰到第一个叶子节点直接返回当前层数，不存在空节点干扰的问题。面试时如果时间紧张，我会先写层序版本，保证正确性，再谈递归优化的思路。

4.3 完全二叉树深度计算时多算根节点

节点个数优化的核心是判断子树是否满二叉树。常见错误是左右深度计算从根节点本身开始累计，导致左右两边深度始终相等或始终相差固定值，公式算出错误的节点数。

判断是否满二叉树时，左深度计算必须从 root->left 开始沿 left->left 走到底，右深度从 root->right 开始沿 right->right 走到底。如果从 root 本身开始数，得到的是整棵树的边界深度，和当前子树不是一回事。

也可以把边界深度计算封装成一个独立函数：

int getLeftDepth(TreeNode* node) { int depth = 0; while (node) { depth++; node = node->left; } return depth; }

这样调用时传 root->left 和 root->right，语义更清晰。强烈建议在写这种带公式的代码时，加一个包含空节点、单节点、三层满二叉树的测试用例，跑一遍确认输出再提交。

4.4 路径回溯忘了 pop_back，路径被污染

路径问题如果输出出现明显拼接错误，先检查递归返回处有没有 pop_back。我见过一个特别隐蔽的错误：在叶子节点处直接 return，但忘了在 return 之前把节点从 path 中弹出。因为这个路径已经存进 result 了，字符串是深拷贝，所以 result 没问题，但 path 里残留了这个叶子节点。回到上一层后，如果还要遍历兄弟分支，path 就多了不该有的节点，导致后续所有路径全部错位。

修复方式是在叶子节点 return 前，或者 return 后统一 pop。更保险的做法是在每一处递归调用返回后都执行 pop_back。我习惯把“加入节点”和“离开节点弹出”成对看作一个整体，每次写完递归都数一遍是否有遗漏的 return 分支。

4.5 调试技巧：打印递归调用轨迹

二叉树递归看不见摸不着，瞎猜没有意义。我给自己的递归函数加带缩进的打印，效果很好。例如求最大深度时：

int helper(TreeNode* node, int depth) { if (node == nullptr) { cout << string(depth * 2, ' ') << "depth " << depth << ": null" << endl; return 0; } int l = helper(node->left, depth + 1); int r = helper(node->right, depth + 1); cout << string(depth * 2, ' ') << "node " << node->val << " l=" << l << " r=" << r << endl; return 1 + max(l, r); }

这个输出会把递归的调用顺序、返回值变化全部展示出来。遇到递归结果与预期不符，对照打印一层一层看，基本都能定位到是终止条件错了、返回类型错了，还是处理顺序反了。这个方法在训练营里被叫做“给递归拍X光片”，比盯着代码发呆高效得多。

5. 训练营复盘：一张速查表把专题2串起来

5.1 题型-遍历顺序-返回值速查表

做完专题2，我发现所有题都可以抽象成一张小表，刷题时对照这个表能快速定位思路：

这张表不是让你背，而是帮你建立一个快速反应：看到“深度”想到后序，看到“交换”想到前序或层序，看到“比较两棵树”想到双参数递归。一旦形成这种条件反射，大部分二叉树题都不再是全新题，而是某种已知模型的变形。

5.2 我的三条实战心得

第一条心得：递归最重要的不是“写得出来”，而是“讲得清楚”。训练营里很多人看题解秒懂，合上书自己写就卡住，原因就是没把递归三要素讲给自己听。下次可以先拿一张白纸，把返回值、终止条件、单层逻辑写出来，再写代码，正确率会高很多。

第二条心得：能画图就不要空想。遇到对称二叉树或者路径回溯，在草稿纸上画一棵只有三个节点的最小树，手动模拟一次递归，比看十遍题解都有用。很多“不明所以”的代码，在纸上跑过一遍后，逻辑就通了。

第三条心得：专题2的题目不要只做一遍。第一遍重在理解，第二遍最好隔两三天再做，第三遍可以尝试用不同遍历顺序或迭代法重写。重复不是刷题数，而是让递归思维真正变成肌肉记忆。我在训练营坚持这种节奏，到了专题3树形DP一类题目时，明显感觉轻松很多，因为专题2已经把“返回值传递”这个最难的概念磨透了。

如果你也正卡在二叉树专题2，别着急。这一周每天写代码前，先按三要素拆一遍题，再动手写，一周之后你会回来感谢这个习惯的。