算法训练营第十四天二叉树2到了第十三天我们基本上把二叉树的骨架摸清了节点结构、树的定义、递归遍历的套路。那十四天干嘛两个字深化。二叉树2这个阶段重点不再是你能写出递归版的前中后序遍历而是你要真正理解递归栈到底是怎么走通的迭代怎么模拟递归层序怎么用队列一次搞定以及最容易被问到的那几个经典场景——树的深度、对称、路径和构造。说白了前面的内容是让你认识二叉树这一天开始是让你会玩二叉树。这期内容适合什么人正在刷代码随想录、跟随任意打卡训练营的初学者或者是面试前想把二叉树常见题型一次性厘清的人。我在这个阶段最大的感受是树的题会递归和不会递归完全是两种体验。而迭代遍历这一关是很多人的分水岭——有人认为反正递归能做了迭代没必要结果一遇到层序、刷新树结构、或者要求空间复杂度、不能爆栈的场景整个人就蒙了。所以这篇文章我会把命令行式的伪代码、真实源码、时空复杂度分析以及我在实际调试中踩过的坑一起整理出来。1. 内容整体设计与思路拆解1.1 为什么第二关专门啃遍历和经典题型训练营把二叉树拆成两到三天的模块是有讲究的。第一天解决是什么第二天解决怎么用。一旦过了第二天后面的回溯、动态规划、图论都会反复跟树打交道。你想想很多递归套路其实本质都是在树上做决策的变体递归终止条件对应空节点递归体对应左右子树的分支。这个意识只有在你对遍历滚瓜烂熟之后才会自然浮现。二叉树2这一天的设计思路通常是这样的逻辑链先用递归把三种深度优先遍历前序、中序、后序写熟练这是所有后续操作的地基。再引入迭代遍历因为面试题或某些限制场景不允许你无脑递归比如树很深时递归会爆栈这一步也是在帮你理解递归其实是编译器帮你维护了调用栈。接着用队列实现广度优先层序遍历这个非常直观——每次把一层的节点全部入队再逐一出队处理。然后围绕遍历结果做文章根据遍历序列构造树、判断树是否对称、计算深度、统计路径总和等等这些才是面试官真正想考的理解深度。1.2 先搞清楚递归三要素再说别的我不知道你是不是跟我一样刚开始学递归的时候总想着我能不能用人脑把递归每一步都走完。千万别这么干。人脑的栈容量非常有限递归超过三层就晕了。正确的方式是记住递归三要素明确函数的功能输入是什么输出是什么。找到终止条件什么时候直接返回不再递归。找出等价关系式怎么做一次操作然后递归调用自己完成剩余部分。以计算二叉树深度为例函数功能是返回以当前节点为根的树的高度终止条件是节点为空时返回 0等价关系是当前树的高度等于 1 加上左子树和右子树中较高的那个高度。就这么简单。这个三要素是整个第二关所有代码题的统一方法论。你会发现几乎所有的树题都可以套这个框架差别只在于终止条件怎么写、等价关系式怎么组合。训练营这个阶段每天安排的题目量不大但每一道都值得你反复手写三到五遍直到形成肌肉记忆。2. 核心细节解析与实操要点2.1 深度优先遍历的递归写法顺序决定一切先说一下基础定义。二叉树节点的结构在多数语言里大同小异以当前训练营常用的写法为例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) {} };递归遍历的核心就一句话处理节点的时机。前序遍历是先处理当前节点再递归左子树最后递归右子树中序遍历是先递归左子树再处理当前节点最后递归右子树后序遍历是先递归左子树再递归右子树最后处理当前节点。// 前序遍历根 - 左 - 右 void preorderTraversal(TreeNode* root) { if (root nullptr) return; cout root-val ; // 处理当前节点 preorderTraversal(root-left); preorderTraversal(root-right); } // 中序遍历左 - 根 - 右 void inorderTraversal(TreeNode* root) { if (root nullptr) return; inorderTraversal(root-left); cout root-val ; inorderTraversal(root-right); } // 后序遍历左 - 右 - 根 void postorderTraversal(TreeNode* root) { if (root nullptr) return; postorderTraversal(root-left); postorderTraversal(root-right); cout root-val ; }为什么强调递归顺序因为后续很多看似复杂的题目本质就是在这三种顺序之间做组合。比如判断二叉搜索树的合法性用的就是中序遍历必须递增这一性质求二叉树的最大路径和用的是后序遍历因为你需要先知道左右子树各自的最大贡献才能计算经过当前节点的路径。顺序不是形式主义顺序就是解题钥匙。2.2 迭代遍历用栈模拟递归的完整流程递归为什么好用因为系统帮你压栈了。系统栈里保存了每次调用时的局部变量、参数和返回地址。当你决定不用递归时就得自己维护一个显式栈。前序遍历的迭代写法最简单因为先处理当前节点、再访问左子树天然适合栈的后进先出特性vectorint preorderTraversal(TreeNode* root) { vectorint result; if (root nullptr) return result; stackTreeNode* 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; }这里有个细节新手很容易写反为什么先压右子树再压左子树因为栈是后进先出我们想要下一个访问的是左子树就必须让左子树后进栈、待在栈顶。你稍微推演一个三层的小树就能理解。中序遍历的迭代就没那么直观了难点在于你得先把整棵树的左边界全部压栈然后才能处理节点处理完当前节点后再去遍历它的右子树。vectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* 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; }这个指针移动到最左、再回溯、再转向右的模式是整个迭代遍历中最容易卡壳的地方。我当时的理解方法是把整棵树想象成每个节点有三个时间段——第一次路过时不处理第二次回来时处理处理完再去右边。中序遍历就是中间的时候处理。后序遍历的迭代实现有一个取巧的办法我们知道前序遍历是根左右如果把前序遍历的左右顺序交换得到根右左然后反转结果数组就得到左右根——这正是后序遍历。这个技巧简单可靠不容易写错vectorint postorderTraversal(TreeNode* root) { vectorint result; if (root nullptr) return result; stackTreeNode* 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; }提示想彻底吃透迭代遍历建议在纸上手动画一棵三层的满二叉树把栈的变化过程逐一写出来。这个动作我做了不下五遍每次都有新理解尤其能帮你避开只记代码不记过程的陷阱。2.3 层序遍历队列出场一层的节点全部拿下层序遍历要用队列这是标准的广度优先思路。核心逻辑是先把根节点入队然后循环处理队列每次取出队首节点时把它的左右孩子分别入队。怎么知道哪些节点在同一层在每次循环开始时先记下当前队列的长度 size然后只处理 size 个节点这 size 个节点就恰好是当前层。vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (root nullptr) return result; 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); } result.push_back(level); } return result; }这段代码的另一个用途是锯齿形遍历之字形遍历。你只需要在结果收集时按层号判断一下是否反转即可偶数层从左到右奇数层从右到左。一个布尔变量或者一个层数计数器就解决了。它是层序遍历的变形题面试中出现频率非常高。3. 实操过程与核心环节实现3.1 经典题一翻转二叉树这道题的知名度不用多说几乎每个训练营都会布置。思路很简单对每个节点交换它的左右子树然后递归处理左右子树。TreeNode* invertTree(TreeNode* root) { if (root nullptr) return nullptr; swap(root-left, root-right); invertTree(root-left); invertTree(root-right); return root; }关键点在于交换操作放在递归调用之前前序还是之后后序都可以达成目的但如果你想用层序遍历做这题那就得在每层取出节点后立刻交换它的左右孩子。这题的坑相对较少唯一的提醒是别在 swap 之后再把原左子树存一份重复递归那就成了死循环加重复计算说不定还会把你自己的栈给炸了。3.2 经典题二判断二叉树是否对称对称树的判断表面上像是结构题实际上是把递归玩出了新花样。你要比较的是根节点的左子树和根节点的右子树是否互为镜像。注意不是左子树和右子树完全相同而是左子树的左节点要和右子树的右节点对应左子树的右节点要和右子树的左节点对应。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); }这道题值得反复琢磨的是递归条件的设计。两棵子树同时为空、一个为空一个不为空、值不相等、继续递归四个分支缺一不可。我在训练营复盘时发现很多人写着写着就漏掉了一个为空的情况一旦漏掉遇到非对称树就会直接访问空指针的 val运行时抛异常。3.3 经典题三根据前序和中序构造二叉树这一题可以说是遍历顺序知识点的集大成者。它利用了前序和中序各自的特点前序遍历的第一个元素一定是根节点。在中序遍历中根节点左边的所有元素属于左子树右边的所有元素属于右子树。根据中序中左右子树的元素数量可以从前序中切分出左右子树各自的前序序列。于是问题就可以递归地解决每次取前序的第一个元素作为根在中序里找到这个根的位置算出左子树的大小 leftSize然后递归构造左子树和右子树。TreeNode* buildTree(vectorint preorder, vectorint inorder) { return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); } TreeNode* build(vectorint pre, int preL, int preR, vectorint in, int inL, int inR) { if (preL preR) return nullptr; int rootVal pre[preL]; TreeNode* root new TreeNode(rootVal); int rootIndexInInorder inL; while (in[rootIndexInInorder] ! rootVal) rootIndexInInorder; int leftSize rootIndexInInorder - inL; root-left build(pre, preL 1, preL leftSize, in, inL, rootIndexInInorder - 1); root-right build(pre, preL leftSize 1, preR, in, rootIndexInInorder 1, inR); return root; }为了提高效率可以把值到索引的映射提前用哈希表存好这样每次找根在中序中的位置就是 O(1)整体时间复杂度从 O(n²) 变为 O(n)。这个优化在训练营里老师一般会提一嘴但在实际面试中它往往是加分项。3.4 经典题四二叉树的最大深度和最小深度最大深度我们已经聊过了一行核心代码搞定int maxDepth(TreeNode* root) { if (root nullptr) return 0; return 1 max(maxDepth(root-left), maxDepth(root-right)); }最小深度稍微有一点容易错的地方最小深度是从根节点到最近叶子节点的距离所以不能简单地写成1 min(...)。如果一棵树只有左子树没有右子树min 会直接取到右子树的 0导致结果错误。正确写法是int minDepth(TreeNode* root) { if (root nullptr) return 0; 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)); }这个小题目背后的逻辑特别能看出一个人对递归终止条件理解得透不透。很多人刷题刷了很长时间依然会在最小深度这道题上栽跟头不是因为不会递归而是因为没有回到定义里去理解叶子节点这个词的意思。3.5 经典题五路径总和与路径总和 II路径总和一是否存在从根到叶子的路径满足 sum 目标值是递归的经典应用bool hasPathSum(TreeNode* root, int targetSum) { if (root nullptr) return false; if (root-left nullptr root-right nullptr) { return targetSum root-val; } int remain targetSum - root-val; return hasPathSum(root-left, remain) || hasPathSum(root-right, remain); }这里的核心思想是剩余和的传递。你看在每一层递归中我们了结了当前节点的值然后把剩下的目标值往下传。这个思想在后来的回溯、动态规划里会反复出现是必须刻意训练的一个思维模型。路径总和 II 要求返回所有满足条件的路径本质上就是深度优先搜索 回溯。每次从一个节点出发探索左右子树时把当前节点加入 path 列表递归结束后再把节点弹出恢复现场。这个加入-递归-弹出的回溯三连之后在图论和排列组合题里也会反复用到值得专门练到指尖记忆的程度。4. 常见问题与排查技巧实录4.1 递归导致栈溢出怎么办树特别深比如退化成链表的斜树时递归深度可能达到上万层程序直接爆栈。遇到这种场景迭代遍历或手写栈的解法就是救命稻草。不过在一场技术面试里如果你能先写出递归版本再主动说一句如果树很深递归可能栈溢出我可以改为迭代实现这通常比闭着眼睛直接写迭代更讨喜因为面试官能看到你既有理解能力也有工程意识。4.2 null 指针到处乱飞这是树题里最最常见的运行时错误。任何递归函数的第一步都应当处理空指针的情况。我的习惯是先把终止条件写出来再写递归逻辑。别小看这个习惯训练营里有相当一部分同学提交报错原因就是某个分支没有判空就访问了 -val 或者 -left 这类成员。判断空指针还有一个高级技巧在写compare(left, right)这类成对比较函数时不要一上来就写left-val ! right-val。先处理一边为空另一边不为空的短路判断再处理值比较这样既安全又高效。4.3 层序结果分层错误很多人在做层序遍历时会忘记在循环开始前记录int size q.size()而是直接for (int i 0; i q.size(); i)。问题在于队列在循环过程中会不断 push 新节点q.size() 是动态变化的导致一次会把两层甚至三层的节点混在一起。这个 bug 非常隐蔽因为对于某些树结构结果看起来好像是对的但对照预期输出就会发现层级乱了。用固定变量 size 的记录方式本质上是快照思想在进入本层处理之前把这一层有多少个节点先定好处理的过程中无论队列怎么变我只处理这么多个。这个思想还有一种变体可以在不知道层边界的情况下用哨兵节点比如 nullptr来分隔层两种方案殊途同归。4.4 递归函数返回值的设计困惑写树题时经常要在返回什么上卡壳。到底是返回 void返回 bool返回 TreeNode*还是返回 int我的经验是先问自己我上一层递归需要从这一层拿到什么信息。比如翻转二叉树需要拿到翻转后的子树所以返回 TreeNode*判断对称只需要知道是否相等所以返回 bool层序遍历只需要把结果收集到外部数组所以返回 void 即可。这个思维习惯能避免大量写着写着就走偏的情况。4.5 调试树题的实用技巧——打印中序序列如果一个树的逻辑变量了最快的排查方式是什么不是瞪着眼看代码而是把树拍平成一个序列。我个人最常用的技巧是在关键递归函数的入口或出口打印当前节点的值。比如排查构造二叉树问题时打印每个递归区间的前序片段和中序片段你能非常直观地看到左子树和右子树的拆分是否合理。还有一个更省事的手段写一个二叉树序列化的辅助函数比如按前序遍历输出空节点记作 #。这样你就能用一行字符串来验证一棵树长什么样。训练营里后段的题目比较依赖这种验证方式提前掌握后面会非常省力。4.6 常见问题速查表症状原因解决办法层序结果乱层循环条件用动态 q.size()循环前记录 size 固定层节点数最小深度算成 1直接取 min(左右子树深度)单独处理左右子树为空的情况前序构造树越界左右子树区间切分错误用 leftSize 推导边界并用哈希表快速定位根对称判断误报 true比较时用了 left-left 与 right-left镜像比较应为 left-left 与 right-right递归爆栈树退化成链表且递归过深改用迭代遍历或显式栈5. 当天的自我检验清单学了一天怎么知道自己是真懂了还是假装懂了我建议你拿这五道题做一下盲写测试翻转二叉树、对称二叉树、二叉树的最大深度和最小深度、层序遍历、前序中序构造二叉树。如果是看着答案能写出来那是认识;合上答案能写出来那是掌握;换一道变体能做出来比如从后序和中序构造二叉树那才是内化。顺便说一句很多训练营会把二叉树2安排在第十四天并不是因为前面十三天有多难而是因为第十四天之后树的题目会大量应用到回溯和动态规划的思想。如果你在这里只是抄了一遍代码而没有认真复盘递归三要素后面遇到 在树中求最长路径在树中求最大 BST 子树 这种题你就会深刻体会到什么叫地基不牢地动山摇。另外关于做题数量我个人的建议是这一天的题不在多在于重复。我当时同样的五道核心题每天花 20 分钟手写一遍连续写了三天直到闭着眼都能把堆栈变化推演出来。这个笨功夫在后面的图论和回溯题目里给了我巨大的回报。二叉树2这个模块表面上看只是多了几个新代码模板实际上是让你完成一次思维方式的转变从我不是很清楚递归内部发生了什么但我能写到我能预测每一层递归进出的时机和状态。这个转变一旦完成后面不管遇到什么树的变体题你都能迅速把它分解成已知问题的组合。这也是训练营把这一天的内容单独拎出来讲的原因——它不是过渡它是质变的起点。