企业官网建设流程全解析

如果自己闷头刷过两周算法题，你大概能体会训练营DAY15这种位置有多微妙：栈和队列刚过去，哈希表刚过去，链表也已经收尾，到二叉树这里先练了两天遍历，刚开始觉得“递归模板背下来就行”，结果进入第六章二叉树part03之后，题目的画风突然从“按照某种顺序把节点打印出来”变成了“翻转它、判断它是不是对称的、计算它的深度”。同样是二叉树，从遍历期到操作期，思路跨度其实非常大，很多人在这一晚卡住，付出的时间远超计划。

DAY15这个节点，在我实际刷题体验里是二叉树从“能看懂代码”到“敢自己写递归”的分水岭。如果把前面两天比作学走路，part03就是第一次真正跑起来，而且一上来就是四道题：翻转二叉树、对称二叉树、求二叉树的最大深度、求二叉树的最小深度。这四道题都不算难，但每一道背后都藏着一个递归或者迭代的关键习惯，练到了就是后面几十道树题的地基，练不到就会在后续二叉搜索树、最近公共祖先、路径总和这些题目上反复吃苦头。

这篇文章我就以DAY15的打卡视角，把这四道题我自己是怎么想的、怎么写代码、怎么踩坑的完整过程拆开讲一遍。内容会覆盖递归三要素、迭代写法、边界条件，也会把最容易让人犯迷糊的最小深度这个坑单独拎出来说。不管你是正好跟到这一天，还是已经刷完二叉树想回头补课，看这篇文章都够用。

1. 第15天打卡前，先把二叉树问题归个类

DAY15的训练内容我拿到手之后，第一反应是去翻前面的笔记，因为part03的题目不再像遍历那样只要按模板走就行。翻转二叉树要动手改树的结构，对称二叉树要在两棵子树之间做对比，最大深度和最小深度则是要提取一棵树的某个数值特征。这其实代表了二叉树题目的三种常见形态：修改结构、比较结构、统计属性。

把这三类分清楚非常重要，因为它们的思考方式完全不同。修改结构类，核心是想清楚“我站在当前节点上要做什么操作”；比较结构类，核心是想清楚“两棵子树之间要传递什么信息”；统计属性类，核心是想清楚“子树返回给父节点的数据到底代表什么”。训练营把这几道题放在同一天练，就是希望你在一晚上把这三种思维模式都触发一遍。

1.1 训练营的part03到底想练什么

part03这一梯队，从顺序上讲接在二叉树遍历之后，处在“认识树”和“利用树”的中间段。因为前面已经掌握了几种遍历顺序，现在你完全可以用任何一种遍历去解决新题。但训练营给出的建议是：能递归就递归，少用迭代。不是迭代不好，而是这个阶段的目标就是锻炼递归直觉。

我自己的理解是，part03是在强制训练一件事：碰到任何二叉树问题，你都要能快速判断出递归函数应该返回什么。比如翻转二叉树，函数返回的是翻转后的根节点；对称二叉树，函数返回的是两棵子树是不是互为镜像；最大深度和最小深度，函数返回的是以当前节点为根的子树深度值。返回值的类型和含义想清楚了，整道题的解法就完成了一大半。

所以到了part03，再看题目就不能只盯着“我用什么遍历顺序”了，而是要先回答三个问题：

• 递归出口在哪？通常是空节点，有时也处理叶子节点。
• 当前层要做什么？可能是交换、可能是比较、可能是累加。
• 子树要返回什么？可能是翻转后的节点，也可能是布尔值或深度值。

这三个问题想透，代码基本能一次写对。

1.2 解决这些题之前，先确认两个基本事实

第一个基本事实：二叉树天然是递归结构。一棵树的左子树和右子树，本质上还是二叉树，所以树的问题大部分可以转化成子问题。这种自相似性决定了递归解法通常是先写起来最直觉的。只要你找准了“子树返回给父节点什么”，递归代码往往就三四行。

第二个基本事实：所有递归都必须有终止条件。二叉树递归题里最常用的终止条件是空节点，也就是 root == nullptr 时返回某个基准值。对深度题来说，空节点返回0；对对称题来说，两个空节点相遇要返回true；对翻转题来说，空节点直接返回nullptr就可以。

这两个事实在不同题目里拼出了完全不一样的代码，但它们的内核是同一个，我整理成表格放在下面，方便你每天复盘对照。

这个表我后来每次写树题都会先默背一遍。它看起来简单，但能逼你把每一道题的“递归契约”想清楚。

2. 翻转二叉树：递归交换的每一步都要“想清楚当前层做什么”

翻转二叉树的题面很直接，输入一棵二叉树，把所有节点的左右子树都交换一遍。比如根节点是1，左孩子是2，右孩子是3，翻转之后就变成左孩子是3，右孩子是2，并且这个操作要递归地应用到所有子树上去。

我第一次做这道题时，第一反应是“能不能用层序遍历，把每一层的节点全部翻转一遍”。理论上可以，但代码会写得比较绕。等到看完训练营的模板，才意识到递归解法才是最有几何直觉的写法。

2.1 直觉来源：一棵树可以被拆成无数个重复子问题

翻转整棵树，本质上就是先翻转左子树，再翻转右子树，最后把根节点左右换一下。而翻转左子树这件事，和翻转整棵树是同一个操作，只是作用范围变小了。这就是递归能够成立的直接原因。

递归写法其实是最符合这个直觉的：

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

这里用的是后序遍历思路：先递归处理左右孩子，回到当前节点时只做交换。核心是最后返回 root，因为父节点需要拿“已经翻转完成的子树”去继续拼接。很多人会把 return root 漏掉，看起来本地测试也过了，一旦做嵌套子树时就发现整棵树结构不对，原因就是父节点拿到的是空。

如果你用的语言允许直接交换对象引用，也可以写成常见的两个递归调用的形式，逻辑没有区别：

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

注意这里用的是前序逻辑：先交换当前节点左右孩子，再去递归处理交换后的孩子们。两种写法都正确，因为翻转操作是可交换的，先翻转子树再交换根节点，和先交换根节点再分别翻转两边，最终得到的树结构是一样的。

2.2 为什么中序遍历在这里是个陷阱

如果你把翻转动作放在中序位置，也就是先递归左子树，再交换当前节点的左右孩子，再递归右子树，代码很容易写出问题。因为中序遍历的特点是处理完左子树后回到根节点，而这时候右子树还是原来的右子树，你对它做递归时，它已经因为刚才的交换被换到了左边，处理内容变成旧左子树。

很多新手在这里会陷入“脑子里知道要交换，但递归顺序和交换动作互相干扰”的状态。我的建议很简单：在翻转这颗树上不要刻意走中序思路。既然前序和后序都很干净，就专注用这两种，省去不必要的纠结。

如果非要写非递归版本，用栈模拟就能避免中序混乱：

TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return nullptr; stack<TreeNode*> 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; }

这套迭代写法的本质是用栈模拟前序遍历，每从栈里弹出一个节点，就交换它的左右孩子，再把孩子节点入栈。时间复杂度是O(n)，空间复杂度是O(n)，和递归版本相当。

2.3 做翻转题容易忽略的一件事

做完翻转后记得检查整棵树的“底层结构”，而不仅仅是根节点的两个子节点。因为题目要的是所有节点的左右子树都被翻转，漏掉任何一个子树都算错。我的自查办法是：递归函数一结束，从根节点开始顺着左侧链往下走一遍，再顺着右侧链走一遍，确认它们互相换过位置。虽然多花几秒钟，但能省掉提交时反复试错的成本。

3. 对称二叉树：真正要比较的是“左右两棵子树是否互为镜像”

对称二叉树这道题，题面是给一棵二叉树，判断它是不是轴对称的。比如一个满二叉树，第三层从左到右是3、4、4、3，那就是对称的；如果是3、4、3、4，那就不是。

这道题最大的误区，就是以为“只要判断每个节点的左右孩子值相等就行”。这只能保证一个节点自己的两个孩子相等，完全没法保证整棵树的镜像对称。真正的判断方式，是在根节点处把树劈成左右两半，然后递归比较：左子树的左孩子要和右子树的右孩子相等，左子树的右孩子要和右子树的左孩子相等。

3.1 对称不是“相等”，是“互为镜像”

我用一个生活化的例子来解释：你站在一面镜子前，镜子里的你和真实的你是对称的。镜子里的“左手”，对应你身体右边的“右手”。所以比较双方时永远是错位的：外侧比外侧，内侧比内侧。

对应到二叉树上，根节点的左子树和右子树就是镜子两侧。比较时要这样配对：

• 左子树的左孩子 对比 右子树的右孩子
• 左子树的右孩子 对比 右子树的左孩子

说白了，它是一个跨越两棵树的递归比较。你没法在一个节点的递归函数里同时拿到“左孩子的左孩子”和“右孩子的右孩子”之外的信息，除非递归函数的参数同时接收两个节点。这就是对称题和翻转题最大的区别：翻转题递归函数只需要一个参数，对称题递归函数至少需要两个参数。

3.2 递归的双参写法

最干净的方式是单独定义一个比较函数，参数是两棵树：

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; 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); }

递归出口这里要小心：只有两个节点同时为空才返回true；两个节点一个空一个不空，说明结构已经不对称了，返回false；都不空但值不同，也返回false。有人会把“一个为空”和“两个为空”合并处理，那会漏掉结构不对称的情况。

我自己喜欢先写两个空节点的判断，再写一个空节点的判断，最后写值不相等判断。顺序固定下来后，遇到类似的双树比较题也能照搬套路。

3.3 用队列进行的迭代对比

对称二叉树也可以不用递归，而是用队列模拟逐层对比。每次从队列里取出两个节点，一个对应左子树侧，一个对应右子树侧，然后按照错位配对的方式把它们的四个孙辈孩子按顺序压入队列。

bool isSymmetric(TreeNode* root) { if (root == nullptr) return true; queue<TreeNode*> q; q.push(root->left); q.push(root->right); while (!q.empty()) { TreeNode* leftNode = q.front(); q.pop(); TreeNode* rightNode = q.front(); q.pop(); if (leftNode == nullptr && rightNode == nullptr) continue; if (leftNode == nullptr || rightNode == nullptr) return false; if (leftNode->val != rightNode->val) return false; q.push(leftNode->left); q.push(rightNode->right); q.push(leftNode->right); q.push(rightNode->left); } return true; }

队列版有一个细节：要让空节点也入队。因为对称性不只体现在值上，还体现在结构上，某一边少了一个节点，另一边多了一个节点，照样不是对称。不少人在写迭代版本时习惯性地跳过空节点，结果结构不对称的用例直接漏判。

关于这套迭代写法的耗时，每个节点进队一次、出队一次，复杂度仍是O(n)。队列最大长度出现在最宽的那一层，所以空间复杂度最坏也是O(n)。

4. 最大深度与最小深度：边界条件决定你能AC还是掉坑

求二叉树的深度，看起来就是递归里加个1，但最大深度和最小深度的边界处理完全不一样。最大深度是从根节点到最远叶子节点的节点数，最小深度是从根节点到最近叶子节点的节点数。这里的关键词不是“深度”，而是“叶子节点”。

很多人做最小深度时单纯把最大深度代码里的 max 改成 min，结果提交时各种错。原因我在4.2里细说。

4.1 最大深度：递归后序最简单

递归写法返回的是以当前节点为根的子树深度，空节点深度为0，当前节点深度等于左右子树深度中的最大值再加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); }

这其实是后序遍历：先拿到左右子树的深度，再回根节点汇总。对树结构来说，深度可以等价于层数，你甚至可以几行代码就测出来，二叉树有多少层。

迭代写法用层序遍历，每遍历一层 depth 加1，最直观：

int maxDepth(TreeNode* root) { if (root == nullptr) return 0; queue<TreeNode*> q; q.push(root); int depth = 0; while (!q.empty()) { int size = q.size(); depth++; for (int i = 0; i < size; ++i) { TreeNode* node = q.front(); q.pop(); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return depth; }

层序版本唯一的坑是每次进入 while 前要先记录当前队列长度。如果不记录，直接在循环里处理所有弹出节点，你就会把下一层刚加进去的节点也数进当前层，深度计算直接错位。所以那一句 int size = q.size() 是必写的。

4.2 最小深度：空子树不算路径

最小深度题面强调“到最近的叶子节点”。叶子节点是指左右孩子都是空的节点。这意味着，如果一个节点只有右子树，它的最小深度不能走左边那条不存在的路径，否则会出现“从根到不存在的空节点”这种错误路径。

错误版代码长这样：

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

如果根节点只有右子树，左子树递归返回0，这个代码就会直接给出最小深度1，但实际上根节点自己不是叶子节点，最近的叶子在右子树深处，正确答案应该是右子树深度加1。所以这个错误版遇上一棵单侧树就会翻车。

正确递归解法要分三种情况处理：

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

第一种情况，当前节点就是叶子，直接返回1；第二种情况，只有左子树或只有右子树，不能取空的那一侧，只能继续走存在的那一侧；第三种情况，左右都有孩子，才可以用 min。这样处理之后，最小深度的递归版本就没有歧义了。

用层序遍历做最小深度更快，因为一旦遇到第一个叶子节点就能立即返回当前深度：

int minDepth(TreeNode* root) { if (root == nullptr) return 0; queue<TreeNode*> q; q.push(root); int depth = 0; while (!q.empty()) { int size = q.size(); depth++; for (int i = 0; i < size; ++i) { 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; }

层序版本的优势是平均情况下不用遍历整棵树，找到第一个叶子就返回，效率比递归高。但别忽略循环里对左右孩子的空判断，漏写会出现空指针访问错误。

4.3 深度题的复杂度与适用场景

递归和迭代的时间复杂度都是O(n)，空间复杂度递归版最坏是链式二叉树O(n)，最好是完全二叉树O(logn)；迭代版的空间复杂度始终由队列最大长度决定，最坏也是O(n)。两者在实际比拼中差距不大，主要看你的思维习惯。

如果题目只是求深度，我推荐递归版，代码最简短。如果题目后续还要同时处理层序相关的逻辑，比如输出每一层的节点，那层序遍历就是更好的选择，因为 depth 天然和节点所在层绑定，省得再维护额外变量。

5. 我的DAY15复盘：从踫壁到条件反射

前面四节把题目讲完了，现在说点真正让我那天晚上花掉额外时间的踩坑记录。这些坑看起来很小，但每一个都真实消耗过我的调试时间，也基本能在未来每道二叉树题上复现，不夸张。

5.1 我在part03踩过的三个坑

第一个坑，翻转二叉树用中序逻辑写。我一开始觉得“反正每个节点都会访问到，放哪交换都一样”，结果递归顺序和交换动作互相干扰，翻转后左子树和右子树各有一侧没有彻底翻。排查的时候，我在纸上画了三层树，眼睛都快看花了才定位到问题。从中我学到的教训是：涉及结构修改的递归，处理动作的位置本身就是逻辑的一部分，不能随手放。

第二个坑，对称二叉树把返回值类型想成单棵树的递归。我最初递归函数的参数只有一个 root，想靠返回bool不断向上传递，结果写到一半发现没法同时比较左子树的右孩子和右子树的左孩子。后来才明白：判断两棵树的关系，递归函数至少得有两个入口参数，这和普通遍历是两回事。

第三个坑，最小深度直接套最大深度模板。我交了一版 max 改 min 的代码后，遇到一个只有右子树的用例直接期望失败。那一刻才真正理解训练营在题解里反复强调的“叶子节点”三个字有多重要。边界条件是这类题目的灵魂，模板可以背，边界条件不能背。

5.2 建议的刷题顺序和时间分配

DAY15这四道题，我建议刷题顺序是：翻转二叉树、对称二叉树、最大深度、最小深度。前两道练“修改结构和比较结构”，后两道练“统计属性”。交换和对比都是递归的经典骨架，先练它们，写深度的递归时会顺畅很多。

时间分配上，我当晚大致用了两小时出头。每道题先自己思考十五分钟，不出来了再看模板。看懂模板后，合上答案自己默写一遍，再把递归版本改成迭代版本。默写这一步非常重要，它能把“我看懂了”变成“我能写出来”，两者隔着一次真正的输出。

5.3 给后面几天同学的一点实操建议

如果你正在训练营DAY15附近徘徊，我给你三个实用建议。

第一，做题时每道题都先问“递归函数返回什么”，再往下写。把返回值写在注释里，代码自然就有骨架了。第二，所有递归题都把空节点判断写在第一行，不管是判空返回0还是返回nullptr还是返回true，先处理最简情况。树题递归如果卡住，九成是出口没放对位置。第三，写完成功解法后，立刻把递归版改写成层序迭代版，因为这个操作能训练你两手抓：递归思维过关，迭代写法也不生疏。

我自己的体会是，DAY15这一天的题目并不难，难的是你能不能从“会做这几道题”跳到“会用递归处理结构关系”。这种跳动靠刷题量堆不出来，靠的是每次写完代码后真的在纸上画一棵小树，把递归调用过程完整走一遍。只要这一天的题吃得透，后面遇到路径总和、二叉搜索树验证、最近公共祖先时，你会明显轻松很多。