企业官网建设流程全解析

做过算法训练营的人都知道，day06是一个很有意思的分水岭。前五天还在数组、链表、哈希表这些“线性结构”里打转，到了第六天突然被丢进二叉树，很多人第一次写递归写到怀疑人生。卡码算法训练营day06的题单，基本就是二叉树遍历的集中轰炸：前序、中序、后序、层序，递归版、迭代版，一套组合拳下来，能把基础打得非常扎实。这篇文章就把我刷完day06的完整思考、踩坑过程和最终沉淀下来的模板写出来，给正在啃这块的朋友一个参考。

你可能会问，day06到底解决什么问题？说白了就两件事：一是彻底理解二叉树的三种深度优先遍历和一种广度优先遍历，二是把递归和迭代两种实现方式都写顺。这两件事看似简单，实际是后面所有二叉树题目的地基——最大深度、最小深度、路径总和、翻转二叉树、对称二叉树，这些题全部建立在“会遍历”的前提上。所以day06的定位不是“会做几道题”，而是“把遍历写进肌肉记忆”。

这篇文章适合谁？零基础刚跟完训练营前五天、准备硬啃二叉树的新手，以及刷过一些题但遇到二叉树就发怵、想系统梳理一遍遍历模板的输出型学习者。我尽量不堆术语，用你能直接抄走的代码和结论来讲。

1. 内容整体设计与思路拆解

1.1 训练营前五天的知识铺垫与衔接逻辑

先说个趋势。大多数算法训练营的前五天，安排的都是线性结构和查找类题目：数组的二分查找、链表的双指针、哈希表的计数与去重。这些内容的共同点是“数据是一个挨着一个的”，你用循环也好、用递归也好，思考方式还是顺序推进。到了二叉树，数据结构第一次变成了“分叉”的形态，一个节点下面有两个分支，而且两个分支还可能长得很不一样。

day06选在这个节点切入二叉树，逻辑上非常顺。因为树本身就是递归定义的：一棵树是根节点加上它的左子树和右子树，而左子树和右子树各自又是一棵树。所以遍历一棵树，最自然的写法就是递归。前五天里，如果你在链表那几天写过递归反转链表，或者写过递归求阶乘，那你已经见过递归的壳子；day06要做的是把递归真正当成“分治”工具来用——不是只处理一层，而是让函数自己处理“子树”这种子问题。

训练营的题单设计也很有意思，它没有一上来就放“翻转二叉树”这种需要点灵感的题，而是先用最朴素的前中后序和层序遍历，让你把“每次访问节点时做什么”这件事练明白。等你遍历写顺了，后面的题无非就是在遍历过程中多加一个判断、多传一个参数而已。

1.2 三种深度优先遍历是一次“思维升级”

很多人在day06之前，对“前序、中序、后序”的记忆方式是背口诀：前序是根左右，中序是左根右，后序是左右根。背口诀没有问题，短期应试够用，但训练营day06的题单会很快让你发现，单靠口诀是写不对递归代码的。

原因在于，口诀只告诉你“输出顺序”，没告诉你“递归调用的时机”。举个例子，前序遍历的代码框架是：

void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; vec.push_back(cur->val); // 前序：先处理根 traversal(cur->left, vec); // 再递归左子树 traversal(cur->right, vec); // 最后递归右子树 }

中序遍历的不同点只有一行，就是vec.push_back(cur->val);从第一行挪到了递归左子树之后。很多初学的人会疑惑：我已经输出根了，为什么递归左子树之后还要递归右子树？根节点的值不是已经记录了吗？这里的关键在于，所谓“遍历顺序”描述的是“访问节点这个动作”在三层递归骨架里的位置，而不是说某个节点只被走到一次。整个递归过程会先沿着左子树一路深入到最底层，然后逐层回退，每个节点实际上被经过三次——只是你在哪一次“动手记录值”，决定了它是前序、中序还是后序。

想明白这一点，你再看递归代码就不再是背模板了，而是在看“在哪个时机插入自己的业务逻辑”。day06做这层思维升级，比多做十道题都值。

1.3 迭代法为什么值得同步搞懂

训练营day06几乎必然包含迭代遍历的题目，很多新手会抱怨：递归明明能过，为什么还要写迭代？这是我在群聊和评论区里看到最多的疑问。

答案很简单：为了搞懂“栈”。递归的本质是操作系统帮你维护了一个调用栈，你写递归的时候不用管栈的入栈出栈，但代价是有递归深度限制和额外开销。迭代遍历则是你亲手维护一个栈，流程完全可控。面试的时候，有些考官会专门让你用迭代写一遍中序遍历，如果你完全没练过，当场就会意识到问题。

我刚刷day06的时候，也觉得迭代版前序遍历很简单，但迭代版中序遍历怎么写都别扭。后来才明白，前序遍历之所以迭代好写，是因为“先处理根节点”这个动作天然配合栈的“先入后出”；而中序遍历要求先处理左子树，就需要用一个指针不断往左压栈，直到没有左孩子，才开始弹栈并处理节点，再转向右子树。这个“指针+栈”双重循环的结构，本质上是在模拟递归调用栈的行为。搞懂它，你对递归的理解会加深一大截。

2. 二叉树的定义、建树与核心概念细节

2.1 节点定义与建树实操

刷题里的二叉树，通常不需要你真正去“建树”，题目已经给你根节点了。但为了理解代码，节点的定义必须烂熟于心。C++写法是：

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

这里有一个容易忽略的细节：构造函数里的left(NULL), right(NULL)，保证了你创建一个节点时左右指针是空的。如果你在本地调试时自己写构造函数而漏了初始化，后面访问左右孩子就会拿到野指针，直接段错误。面试手写代码的时候，这一点也经常被拿来当考察点。

你可以用层序序列来反推一棵树，比如序列[3,9,20,NULL,NULL,15,7]对应一棵三层的二叉树。我自己调试时习惯写一个简单的辅助函数，根据层序数组构建树，方便本地造测试用例；训练营的题单不需要你封装这个功能，但本地练习时非常有用。

2.2 递归三要素是“通用解题脚手架”

day06最大的收获，是它逼着你把递归的写法格式化。写过很多次递归之后，我发现任何一个递归函数都可以拆成三件事：

1. 确定函数签名和返回值：这个递归函数要完成什么，需要哪些参数。
2. 确定终止条件：什么情况下递归不再继续，通常是节点为空。
3. 确定单层递归的逻辑：这一层要做什么操作，以及如何递归调用下一层。

以中序遍历为例：

• 函数签名：void traversal(TreeNode* cur, vector<int>& vec)，把结果收集到vec里。
• 终止条件：if (cur == NULL) return;空节点直接返回。
• 单层逻辑：traversal(cur->left, vec); vec.push_back(cur->val); traversal(cur->right, vec);

你会发现，如果单层逻辑里加一个“if (cur->val == target)”的判断，这就是一道查找题；如果加一个“累加值”的变量，这就是一道路径总和题。day06的递归遍历，练的是这个“脚手架”本身，脚手架搭得稳，后面你套什么都顺手。

2.3 前中后序的“打印位置”记忆法

这里分享一套我试过之后觉得最好用的记忆方式，比口诀靠谱得多：不要记“根左右”，而是记“打印语句放在哪一行”。你先把递归框架固定下来：

void dfs(TreeNode* root) { if (root == nullptr) return; // 位置A dfs(root->left); // 位置B dfs(root->right); // 位置C }

在位置A写打印语句，就是前序遍历；在位置B写，就是中序遍历；在位置C写，就是后序遍历。这个理解方式的好处是，你能直接把它推广到所有二叉树递归题：你只需要想清楚“我要在递归的哪个时机处理当前节点”。

比如计算二叉树的最大深度，你要在位置C做处理——因为你需要先知道左子树和右子树的深度，才能算出当前节点的深度。而判断两棵树是否相同，你要在位置A做处理——先把两个根节点比一比，如果不相等直接剪枝返回。

这种思维一旦建立，你看任何二叉树题都不再是一件新事，而是“在哪个位置加什么代码”的事。

3. 完整代码实现：递归版与迭代版

3.1 前序遍历：递归版与迭代版

前序遍历的递归版最直白，先把根处理掉，然后一路往左子树钻，钻到底再回头处理右子树。

class Solution { public: void preorder(TreeNode* root, vector<int>& result) { if (root == nullptr) return; result.push_back(root->val); preorder(root->left, result); preorder(root->right, result); } vector<int> preorderTraversal(TreeNode* root) { vector<int> result; preorder(root, result); return result; } };

迭代版前序遍历的套路是：先把根节点压栈，然后循环弹栈，处理完弹出节点后，先压右孩子、再压左孩子。为什么先压右再压左？因为栈是后进先出，你希望下一次弹出的是左孩子，就得让左孩子后进栈。

class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> result; if (root == nullptr) return result; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); result.push_back(node->val); if (node->right) st.push(node->right); if (node->left) st.push(node->left); } return result; } };

我当时第一次写迭代版前序遍历，犯过一个低级的顺序错误：先压左再压右，结果整棵树的遍历顺序变成了“根右左”。排查了几分钟才发现，问题就是这么简单。记住“先右后左”这个细节，你能省下不少调试时间。

3.2 中序遍历：为什么迭代版和前序不一样

中序遍历的迭代版是day06里最劝退的一个，因为它不能套用前序遍历的模板。前序遍历是“边弹栈边处理节点”，但中序遍历要求先处理完左子树，才能处理当前节点，所以你得用一个指针不断往左下走，把所有左孩子压栈，直到最底层。此时栈顶就是整棵树最左边的节点，弹出来处理它，然后让指针移到它的右孩子，再重复这一套。

class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { while (cur != nullptr) { st.push(cur); cur = cur->left; } cur = st.top(); st.pop(); result.push_back(cur->val); cur = cur->right; } return result; } };

这个写法非常优雅，也很有迷惑性。你会发现外层循环的条件是cur != nullptr || !st.empty()，这两个条件缺一不可。如果只写!st.empty()，当root为空时，循环直接就进不去了，结果是对的但逻辑上少了分支；如果只写cur != nullptr，处理完左子树回到根节点后，cur会被更新为右孩子，右孩子为空且栈中还有元素时，循环就停了，结果会漏掉右边的节点。

我建议你把这个代码手抄几遍，然后手动模拟一遍执行过程。拿一棵只有三个节点的树[1,2,3]举例：先把1和2压栈，弹出2，把cur改成2的右孩子（空），此时栈还有1，循环继续，弹出1，cur改成3，把3压栈，再弹出3。你能明显看到“先左后根再右”的顺序是怎么被压出来的。只有亲手推演一遍，迭代中序才会真正变成你的东西。

3.3 后序遍历：两个栈的巧妙复用

后序遍历的迭代版是三种遍历里最绕的，因为它的访问顺序是左右根，意味着根节点要最后才处理。但如果你已经写了前序遍历的迭代版，会发现一个取巧的办法：前序是“根左右”，如果我把前序遍历压栈的顺序反过来，也就是“根右左”，然后把这个结果整体反转，就变成了“左右根”，也就是后序遍历。

代码实现可以这样：按根右左的顺序收集结果，处理的时候先压左孩子再压右孩子，弹栈顺序变成根右左，最后把整个vector反转。

class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> result; if (root == nullptr) return result; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); result.push_back(node->val); if (node->left) st.push(node->left); if (node->right) st.push(node->right); } reverse(result.begin(), result.end()); return result; } };

这个方法我第一次看到的时候觉得很巧妙，但还是建议你在day06就把它当成标配写法，因为它的逻辑清晰，不容易写错。真正的“正统”后序迭代是双栈法或用一个栈加前置标记，技巧性更强，但日常刷题完全用不到那么复杂。先把简单的、不容易错的版本玩熟，等你有余力再去看更高级的写法。

3.4 层序遍历的队列写法速记

层序遍历和前中后序遍历不是一个维度，它用的是队列，不是栈。核心思想是：每一轮循环处理“当前队列里的所有节点”，处理完一轮，就是把二叉树同一层全部处理完毕。

class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (root == nullptr) return result; queue<TreeNode*> que; que.push(root); while (!que.empty()) { int size = que.size(); vector<int> level; for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); level.push_back(node->val); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } result.push_back(level); } return result; } };

这里有一个非常重要的细节：在for循环之前，必须先记录int size = que.size()，而不是直接在for (int i = 0; i < que.size(); i++)里写que.size()。因为每处理一个节点，就会往队列里压入它的左右孩子，队列的size是动态变化的。如果你不事先固定size，for循环可能永远走不完，或者一次处理了超出当前层级的节点，最后分层的逻辑就全乱了。

这个错误我在训练营的讨论区见过好几个人踩过，包括我自己第一次写层序遍历也没反应过来。你只要记住一句话：分层遍历时，循环次数必须用当前层的初始长度锁定。

4. 常见问题与排查技巧实录

4.1 空指针与节点访问问题

二叉树题里最高频的报错就是空指针访问。常见场景有两个：一是递归终止条件漏写了root == nullptr，导致空节点继续被访问root->val；二是判断一个节点的左孩子是否存在时，直接访问root->left->val而没有先判断root->left != nullptr。

我自己的检查习惯是：凡是出现->left或->right的地方，先确认这个节点本身不为空；凡是递归函数的开头第一行，先写终止条件。这个习惯一旦养成，空指针问题几乎可以完全杜绝。

再看一个更隐蔽的坑：如果你想判断一个节点的左子树是否满足某个条件，可能会写if (root->left) recurse(root->left)，但如果你用的是if (root->left != nullptr && root->left->val == xxx)，第二个条件访问前已经确认了左子树非空，就不会有问题。而如果条件顺序写反了，一旦左子树为空，程序直接崩溃。所以记住一条：判断属性和访问属性之间，永远先判断。

4.2 递归返回值的收集错误

递归遍历里，很多人以为函数返回值是void就没问题了，结果发现结果集一直是空的。最常见的错误是把result当成普通参数传值传递，而不是传引用。如果你写的是void traversal(TreeNode* cur, vector<int> vec)，那么每一层递归都在拷贝一份新的vec，最后结果根本没收集到最外层。这是我见过的新手经典错误榜前三。

还有一种情况是递归函数有返回值，但调用的时候没有接收。比如写一个二叉树查找，bool dfs(TreeNode* node, int target)，你写了if (node->left) dfs(node->left, target);，然后发现结果不对，因为子树的返回值被丢弃了。正确写法是if (node->left && dfs(node->left, target)) return true;。这种错误在day06的遍历题里不太明显，但后面做路径求和、判断平衡二叉树时就会集中爆发。

我的建议是：训练营前五天你就可以自己做一个小总结——递归函数什么时候需要返回值，什么时候不需要。需要返回值的情况通常是“子问题的结果会影响父问题的判断”，比如求深度、判断存在性；不需要返回值的情况通常是“我只要把遍历过程的结果收集到外部容器里”。中序遍历就属于后者，深度计算就属于前者。day06的题单正好涵盖了这两种类型，顺手整理一下收益很大。

4.3 迭代版本死循环排查

迭代遍历里，最让人崩溃的问题就是“程序没报错，但就是跑不完”。排除数据量过大的原因后，90%的情况是某个节点的指针没有更新，或者栈的入栈条件写错。

举一个具体的例子：中序遍历迭代版里，如果你在while (cur != nullptr)的内层循环中忘记写cur = cur->left，那么同一个节点会被反复压栈，直到栈溢出或者死循环。这种问题很好排查，你只需要在循环里加一个计数器，如果超过节点总数，就说明循环逻辑有误。

另一个建议是，如果你实在排查不出逻辑错误，就手动跑一个小例子。写一个递归版的输出，再跑迭代版，对比前几个节点的输出顺序，基本能快速定位问题出在左子树的处理还是右子树的处理。

4.4 卡时间与效率的刷题节奏

day06的题量不大，但如果每一道题都从零开始推导，会非常花时间。我的建议是：递归版自己独立写，迭代版先看模板再自己默写。为什么？因为递归版适合练思路，迭代版适合练套路。你只有在套路还不太熟的时候咀嚼一遍，后面写起来才会快。

我自己测下来，一天内完成day06全部题目的节奏大概是：先花30分钟复习递归三要素，然后直接刷递归版的三道遍历题，每道15分钟；接着看迭代版模板，先抄一遍前序，再在不看模板的情况下默写中序，最后尝试自己推导后序；层序放在最后写，因为这道题稍微简单，适合作为放松。

我还发现一个容易影响效率的细节：别在本地反复造数据测试一遍遍打印。线上的判题环境会给你最精确的反馈，本地打印虽然直观，但非常浪费时间。我后来就把打印习惯戒了，改为直接跑用例，心算输出结果，速度提升了一倍不止。

5. 从day06往后看：遍历模板如何延伸到所有二叉树题

5.1 判断树相同、翻转树、最大深度都是同一套递归

如果你把day06的遍历模板掌握扎实，后面很多所谓的“新题”，本质上只是微调。比如判断两棵树是否相同，你只需要同时遍历两棵树，并在位置A比较两个节点的值是否相等：

bool isSameTree(TreeNode* p, TreeNode* q) { if (p == nullptr && q == nullptr) return true; if (p == nullptr || q == nullptr) return false; if (p->val != q->val) return false; return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); }

翻转二叉树呢？其实就是后序遍历，在位置C交换左右孩子：

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

最大深度呢？位置C对左右子树的最大深度做加一操作：

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

这三道题在训练营里通常是day07或者更后面的内容，但它们和day06的关联性非常强。如果你在day06就把“在哪个位置做什么”想明白了，后面看到这类题会非常有底气。

5.2 一套模板应对N道题的思路

写到这里，我想给你一个更实操的建议：不要以“题目”为单位做笔记，要以“遍历模板”为单位做笔记。把day06的四种遍历（前序递归、前序迭代、中序递归、中序迭代、后序递归、后序迭代、层序）整理在一页笔记里，然后把后续遇到的每道二叉树题，归入“这道题是改哪个模板的哪个位置”。

例如，判断是否对称的题，本质上是同时遍历左右子树，并且位置A做比较；求最小深度的题，要注意左右子树是否为空的特殊情况，和最大深度的代码只有两三行的差别；找二叉搜索树第K小的元素，直接可以套中序遍历的模板，因为BST的中序遍历天然是递增序列。

这套思维建立起来，你刷题不再是“今天遇到一道新题”，而是“今天又见到一个旧模板的新用法”。我之前带过的一个学弟就是靠这个方法，在十来天的时间里把二叉树相关的训练营题目全部刷完，后面做树相关的面试题基本没有卡壳过。

说回day06本身的定位，它更像是一个“开关”——从“我会写数组和链表”切换到“我能处理递归定义的树结构”。你不需要在这一天把二叉树的所有花样都吃透，只需要把遍历这件事做到不用想就能写对。后面不管题目怎么变，底子就是这一天的四个遍历。

我个人的体会是，这天的题刷得快不快不重要，重要的是你最终能不能闭着眼睛把前中后序的递归和迭代都默写出来。如果能，那这一天的时间就没白花；如果不能，我建议你隔一天再刷一遍day06的题单，哪怕只是重复做一遍原题，收获都会非常大。