算法学习day20这个标题在打卡群里出现的时候其实是一个分水岭——前面19天都在和数组、链表、哈希表、字符串这些线性结构打交道从这一天开始第一次正式接触非线性结构。如果你也跟过算法学习计划应该能感受到这种节奏安排的用意线性结构是基础中的基础但只靠它们构建不出复杂的抽象模型而二叉树恰恰是第一个能让你真正“递归起来”的数据结构。这篇内容不是面试八股文式的概念罗列而是把我整个第20天学习二叉树的过程、代码、思考、踩坑全部摊开来讲。从建树、四种遍历方式、遍历序列还原二叉树、深度计算到二叉搜索树、AVL旋转、线索二叉树最终落到调试经验和边界条件处理。无论你是刚开始刷题的小白还是已经刷过一段时间但二叉树总是“一写就错”的人这篇都值得你从头到尾过一遍。1. 学到这里才碰二叉树递归思维的全面登场1.1 为什么第20天才轮到二叉树很多刚接触算法的人会疑惑二叉树这么重要为什么不早点学说实话如果你从第5天就学二叉树大概率会学得一头雾水因为二叉树题目的核心不是“树”本身而是围绕树展开的递归、分治、回溯这些思维工具。前面19天用数组、链表练手本质上是在训练循环、指针操作、双指针、哈希表映射这些“底层的肌肉记忆”。有了这些积累第20天学二叉树时你才能把注意力集中在“递归逻辑”上而不是被“这个节点怎么指来指去”绊住脚。这种学习路径设计不是我拍脑袋想的我翻了往期不少通过大厂算法面试的朋友的路线图他们的共同点是线性结构刷得足够扎实之后再进攻二叉树效率反而更高。原因很简单二叉树的代码量不大难的是“递归怎么设计”而递归恰恰是一种需要先“见过足够多循环和栈操作”才能自然理解的高级抽象。1.2 递归三要素终止条件、函数调用、返回值开始写二叉树代码之前必须先把递归的模型在脑子里立起来。很多人递归写得乱不是逻辑不行而是不知道“这一个递归函数到底该干什么、给上层返回什么”。我总结递归三要素每次写递归前先逼自己回答清楚终止条件是什么——也就是什么时候不用再往下递归了。二叉树里最常见的终止条件是节点为空此时返回0或者返回空指针。函数要做什么——这一层递归要处理什么逻辑。是先访问当前节点还是先递归左子树这决定了遍历顺序。返回值怎么处理——子递归的结果如何传给上一层。是求和、取最大值、布尔判断还是拼接字符串举个最简单的例子求一棵树的节点总数int countNodes(TreeNode* root) { if (root nullptr) return 0; int leftCount countNodes(root-left); int rightCount countNodes(root-right); return leftCount rightCount 1; }这段代码看着只有四行但它把递归三要素全用上了终止条件是root为空返回0函数做的事是“数左子树节点 数右子树节点 自己的1个”返回值是节点总数。如果你能把这段代码的逻辑在纸上手动展开一遍——先数左子树、右子树再往上累加——你对递归的信心会立刻上一个台阶。1.3 手动展开递归把“栈”变成可见的东西我强烈建议初学者至少手动展开一次递归调用过程而不是光在脑子里“感觉”。以题目“求树的深度”为例假设一棵树长这样1 / \ 2 3 / 4调用maxDepth(root)时系统会先压栈进入左子树节点2节点2又压栈进入左子树节点4节点4左右为空返回1节点2再进入右子树为空返回0所以节点2这层拿到max(1, 0) 1 2回到根节点后右子树为3深度1最终根节点返回max(2, 1) 1 3。这个过程其实就是把递推公式depth(node) max(depth(left), depth(right)) 1不断展开。你把这个展开过程写一遍看一次系统栈的“后进先出”如何完成回溯比背十个递归模板都管用。我学二叉树第一天就在草稿纸上手动展开了大概十道题的递归过程之后写递归几乎没有再“懵”过。2. 建树与四种遍历代码骨架几乎一样变的是打印时机2.1 先序、中序、后序的本质区别访问时机二叉树的遍历是后面所有进阶操作的基础四种遍历方式必须像条件反射一样熟练。剥开表象它们本质上用的都是同一个递归骨架区别只在于当前节点的访问时机// 先序遍历根 - 左 - 右 void preorder(TreeNode* root) { if (root nullptr) return; cout root-val ; preorder(root-left); preorder(root-right); } // 中序遍历左 - 根 - 右 void inorder(TreeNode* root) { if (root nullptr) return; inorder(root-left); cout root-val ; inorder(root-right); } // 后序遍历左 - 右 - 根 void postorder(TreeNode* root) { if (root nullptr) return; postorder(root-left); postorder(root-right); cout root-val ; }三份代码唯一的区别就是那行cout的位置先序在递归左右子树之前打印中序在左子树递归完之后打印后序在左右子树递归都完成后打印。很多初学者死记“先序中序后序”的定义但真正理解了“打印时机”后你根本不需要背。我给你一个记忆锚点先序的输出顺序决定了你“第一次遇到节点”时的信息中序的输出顺序决定了你“从左子树爬回节点”时的信息后序的输出顺序决定了你“左右子树都处理完”时的信息。这个特性在后面“根据遍历序列还原二叉树”时是决定性的。2.2 层序遍历队列天然匹配逐层推进层序遍历和前面的DFS深度优先思路完全不同它用的是BFS广度优先核心工具是队列。层序的逻辑一句话说清楚从根节点开始每弹出一个节点就把它左右孩子按顺序入队。void levelOrder(TreeNode* root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* node q.front(); q.pop(); cout node-val ; if (node-left) q.push(node-left); if (node-right) q.push(node-right); } }很多人不理解为什么层序用队列而不是栈你可以想成排队叫号——先来先服务根节点先入队它的孩子排在后面然后再轮到孩子的孩子。如果这里用栈后进先出遍历顺序就会变成“沿一条路走到黑”和层序完全是两回事。层序在算法题里最常见的变体是按层输出也就是把每一层的节点单独放在一个vector里。这个需求只需要在while循环外面套一层int size q.size(); for (int i 0; i size; i) { ... }因为你在一开始记录到的size恰好就是当前层的节点数量。2.3 递归与迭代两种实现怎么选面试里常要求你“不要用递归实现遍历”这时候你要会用显式栈模拟递归。以中序遍历为例迭代写法的思路是先沿左子树一路压栈到底后弹栈访问节点再转向右子树。vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); res.push_back(cur-val); cur cur-right; } return res; }迭代写法的意义不只是“避递归”而是让你真正理解递归背后的栈机制。我在学习过程中有一个深刻体会递归写多了人容易变成“递归只会套模板”而手动模拟栈能把递归的每一个中间状态都呈现出来。如果你做二叉树的中序迭代遍历感到别扭说明你对递归的过程还没吃透回去把1.3节的手动展开再做一遍。3. 遍历序列还原二叉树中序序列是那把钥匙3.1 先序中序怎么确定树的样子“知道二叉树的先序和中序如何确定树的样子”是热词搜索里被问爆的问题也是面试手撕代码的高频题。先说结论只要有中序序列再搭配先序或者后序任意一个就能唯一确定一棵二叉树。原因在于先序或后序负责提供“根节点的位置”中序负责提供“左右子树的分界线”。举个例子先序是ABDCE中序是DBAEC。先序第一个元素是A所以A是整棵树的根。在中序里找到A的位置左边是DB右边是EC。于是左子树的中序序列是DB右子树的中序序列是EC。再去先序里看先序去掉A后是BDCE其中BD这部分属于左子树CE这部分属于右子树。再看左子树先序序列的第一个元素B就是左子树的根……这样不断递归切分整棵树就被还原出来了。3.2 代码实现递归切割序列的思路这个题的代码有很多版本我推荐一种用哈希映射优化的写法核心是“不要真的去复制vector子序列”而是用索引范围在原地切割。TreeNode* buildTree(vectorint preorder, vectorint inorder) { unordered_mapint, int pos; for (int i 0; i inorder.size(); i) { pos[inorder[i]] i; } return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, pos); } TreeNode* build(vectorint pre, int preL, int preR, vectorint in, int inL, int inR, unordered_mapint, int pos) { if (preL preR) return nullptr; int rootVal pre[preL]; TreeNode* root new TreeNode(rootVal); int rootPosInorder pos[rootVal]; int leftSize rootPosInorder - inL; root-left build(pre, preL 1, preL leftSize, in, inL, rootPosInorder - 1, pos); root-right build(pre, preL leftSize 1, preR, in, rootPosInorder 1, inR, pos); return root; }这里最关键的计算是leftSize rootPosInorder - inL它表示“左子树有多少个节点”。只要能算出这个数量先序序列里左右子树的边界就可以精确定位。这种递归切分的思想本质上还是“分治”把大问题切成两个独立的小问题分别解决后拼回原树。3.3 为什么“先序后序”不能唯一确定二叉树道理很简单因为先序和后序提供的信息“重叠”了。先序能告诉我们根在最前面后序能告诉我们根在最后面但单凭这两者无法区分“一个节点到底是左孩子还是右孩子”。比如先序是AB后序是BA这棵二叉树可以是根A带左孩子B也可以是根A带右孩子B两种结构完全不同但遍历结果却一模一样。而中序序列恰好提供了“左子树和右子树的分割线”缺失这条分割线还原就会产生歧义。这个知识在面试里不一定直接考但它能帮你建立对遍历序列结构的深入理解。我在刷题时就见过一道变体题给的是“先序后序”要求判断是否能唯一确定二叉树答案就是“当且仅当某子树根只有一个孩子时才不唯一”——这道题如果你理解了上面的原理瞬间就能想通。4. 求二叉树深度四种写法和一个容易混淆的概念4.1 递归写法最顺手但边界别搞错二叉树的深度是热词里的高频搜索项同时也是后面判断平衡二叉树的基础。最经典的递归写法是这样int maxDepth(TreeNode* root) { if (root nullptr) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return max(leftDepth, rightDepth) 1; }这段代码有两个边界要注意。第一空树深度是0不能返回-1否则单节点树的深度会算错。第二理解“1”加的是当前节点这一层。很多人在递归里反复纠结“这层到底加不加”我的建议是在草稿纸上画一个三层的树手动模拟一遍递归展开把每层返回值标出来一次就能彻底清楚。4.2 不用递归迭代和层序计数递归版本虽然好写但有些题目会要求你用迭代。求深度用层序遍历其实非常直观每遍历完一层深度就加1。你只需要在层序代码里每次进入while循环之前记录size q.size()这个size就是当前层的节点数处理完这一层的所有节点后depth。还有一种思路是“单栈模拟DFS”栈里同时存节点和节点所在深度每次弹出时更新maxDepth。这种写法更接近递归栈的模型也更适合改成别的DFS变体题。如果你对递归不熟先用层序遍历理解深度再回头补递归这种学习顺序反而更顺。4.3 深度、高度、层数分清它们之间的换算二叉树里“深度”“高度”“层数”三个概念经常被混用但它们有严格的区分概念定义常见起始值深度从根到该节点的边数根节点深度为0高度从该节点到最远叶子的边数叶子节点高度为0层数该节点位于第几层根节点在第1层在实际算法题里题目经常不严格区分这些起始值比如求深度可能默认根深度为1。遇到这种情况我的习惯是先看样例样例输出能直接告诉我们它用的是哪套定义。不要想当然也不要跟面试官争概念按题目走就行。4.4 平衡二叉树判断深度的进阶应用“判断一棵树是不是平衡二叉树”是深度的直接延伸。平衡二叉树定义是每个节点的左右子树高度差绝对值不超过1且左右子树本身也是平衡二叉树。我见过很多人的第一版代码这样写bool isBalanced(TreeNode* root) { if (root nullptr) return true; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return abs(leftDepth - rightDepth) 1 isBalanced(root-left) isBalanced(root-right); }这个写法在逻辑上没错但效率很差因为每次判断一个节点都要递归求一遍它左右子树的高度导致大量重复计算。更优的做法是“自底向上”在递归求高度的同时判断是否平衡一旦发现不平衡就提前返回-1作为标记。int height(TreeNode* root) { if (root nullptr) return 0; int left height(root-left); if (left -1) return -1; int right height(root-right); if (right -1) return -1; if (abs(left - right) 1) return -1; return max(left, right) 1; } bool isBalanced(TreeNode* root) { return height(root) ! -1; }这个优化后的版本每个节点只被访问一次时间复杂度从O(n log n)降到O(n)。我在做热词里提到的“二叉树求深度”相关题时就经常看到有人因为递归重复计算而超时这个“自底向上带标记返回”的思路是必须掌握的。5. 二叉搜索树中序遍历等于有序序列这件事太好用了5.1 搜索树的定义与查找代码二叉搜索树BST的定义说起来很简单对于任意节点左子树所有节点的值都小于它右子树所有节点的值都大于它。但这句“所有”是重点很多人理解成“只是左孩子小于节点”于是写出错误的验证代码。BST的查找天然适合用循环或递归它的逻辑和二分查找几乎一模一样要查的值比当前节点小就往左走比当前节点大就往右走相等就返回。TreeNode* searchBST(TreeNode* root, int val) { while (root ! nullptr root-val ! val) { if (val root-val) root root-left; else root root-right; } return root; }这段代码的优势是空间复杂度O(1)不需要递归栈。BST的查找时间取决于树的高度平衡情况下是O(log n)但如果树退化成了链表查找就退化成O(n)——这也是为什么后面要学AVL树和红黑树。5.2 插入和删除别把结构弄丢了BST的插入很容易理解就是“找到应该挂的位置然后把新节点挂上去”。但删除操作要分三种情况考虑被删节点是叶子节点直接删掉。被删节点只有一个孩子用孩子替代它。被删节点有两个孩子通常用“右子树中的最小节点”或“左子树中的最大节点”来替代它然后删除那个最小/最大节点。第三种情况里的“替代节点”也叫后继节点或前驱节点。选后继的逻辑是右子树中的最小值一定比左子树所有值大又比右子树其他值小所以把它提上来之后BST性质不会被破坏。这种删除节点的方式也是后面AVL树删除操作里要重复用到的基础。5.3 验证一棵树是不是BST上下界陷阱“验证搜索二叉树”是容易写错的一道题。大多数人第一版本的代码是递归判断左孩子小于根、右孩子大于根但这是错的。考虑这样一棵树根是10右孩子是15右孩子的左孩子是12——按“只比对根”的逻辑12小于15左孩子合法但它在整棵树里却小于10所以不是BST。正确写法要传递上下界bool isValidBST(TreeNode* root) { return validate(root, LONG_MIN, LONG_MAX); } bool validate(TreeNode* node, long long lower, long long upper) { if (node nullptr) return true; if (node-val lower || node-val upper) return false; return validate(node-left, lower, node-val) validate(node-right, node-val, upper); }理解这个上下界的核心是每往左走一层上界就更新为当前节点的值每往右走一层下界就更新为当前节点的值。一旦某个节点超出了它祖先节点给定的范围就可以立即判定不是BST。这道题的变体很多比如允许相等值在左子树出现或者让你判断一棵树是不是“合法的红黑树前身”本质都是上下界思想。6. AVL树旋转平衡的直觉理解6.1 平衡因子和失衡的四种形态AVL树是最经典的平衡二叉搜索树它的核心要求是任意节点的左右子树高度差绝对值不超过1。这个高度差叫“平衡因子”通常定义为左子树高度减右子树高度。每次插入或删除节点后如果某节点的平衡因子绝对值大于1就要通过旋转来恢复平衡。失衡形态一共有四种名字是LL、RR、LR、RL。记忆方法也很简单LL型左子树的左子树过深需要“右旋”一次。RR型右子树的右子树过深需要“左旋”一次。LR型左子树的右子树过深先对左子树“左旋”再对整棵树“右旋”。RL型右子树的左子树过深先对右子树“右旋”再对整棵树“左旋”。6.2 手动模拟旋转不要死记代码旋转的代码说难不难但如果你只是背下来过两天一定忘。我来手动拆一次“右旋”——也就是LL型失衡的修复过程。假设有三个节点k1是根k1的左孩子是k2k2的右孩子是B可以为空。右旋就是把k2提升为根k1变为k2的右孩子原来的B变成k1的左孩子。代码这样写TreeNode* rightRotate(TreeNode* k1) { TreeNode* k2 k1-left; TreeNode* B k2-right; k2-right k1; k1-left B; // 更新高度 k1-height max(getHeight(k1-left), getHeight(k1-right)) 1; k2-height max(getHeight(k2-left), getHeight(k2-right)) 1; return k2; }你仔细看这段代码本质上只做三件事k2接管根的位置k1变成右孩子B换爹。这个过程在树上操作的时间复杂度是O(1)但效果是让整棵子树高度降低一层同时完美保持BST的中序有序性。左旋就是完全对称的操作把方向反过来即可。真正难记的是LR和RL双旋但我的经验是不要硬记双旋把双旋拆成两次单旋。LR就是“先对左孩子做左旋再对自己做右旋”RL就是“先对右孩子做右旋再对自己做左旋”。这样整个AVL的旋转操作就压缩成两条规则而不是四个孤立代码。6.3 旋转的本质压低高度但绝不改变中序顺序为什么AVL用旋转来平衡而不是直接把节点挪来挪去因为在二叉搜索树里旋转是唯一一种既能让树变矮、又能维持BST性质的局部调整手段。你可以把旋转理解成“换位置但维持排队顺序”想象一排人按身高站队AVL的旋转就是几次相邻交换交换完队伍依然有序但整体变得更紧凑。这个理解对后续学习红黑树、跳表都有帮助。红黑树的变色和旋转也是遵循同一个原则——无论如何调整中序遍历的结果绝不能变。如果你在做AVL相关练习时发现旋转后中序遍历变了那一定是代码写错了。7. 线索二叉树把空指针都利用起来7.1 线索化要解决什么问题普通二叉树用递归或栈遍历空间复杂度是O(h)h是树高最坏情况下是O(n)。线索二叉树的思路很“抠门”一个二叉树里有很多空指针——有n个节点的二叉树总共有2n个指针字段其中n-1个指向实际节点剩下n1个都是空指针。线索化就是把这些空指针利用起来让它们指向遍历序列中的“前驱”或“后继”节点这样遍历时就不需要递归或栈了。线索二叉树在教科书里看起来有点“绕”但实际写一遍线索化过程反而比想象中简单。7.2 中序线索化的构造思路线索二叉树的节点结构通常要加两个布尔标记leftTag和rightTag。为0表示指向真实孩子为1表示指向前驱或后继。中序线索化的过程本质上是在中序遍历的过程中记录“上一个访问的节点”通常叫prev然后把当前节点的空指针指向prev或者把prev的右空指针指向当前节点。void inorderThread(TreeNode* node, TreeNode* prev) { if (node nullptr) return; inorderThread(node-left, prev); if (node-left nullptr) { node-left prev; node-leftTag 1; } if (prev ! nullptr prev-right nullptr) { prev-right node; prev-rightTag 1; } prev node; inorderThread(node-right, prev); }这段代码的逻辑是这样先递归左子树处理完左子树后prev正好是左子树的最后访问节点。如果当前节点的左指针为空就让它指向prev如果prev的右指针为空就让prev的右指针指向当前节点。这个“互相拉手”的过程就是线索化的核心。7.3 中序线索树怎么遍历线索化完成后中序遍历可以写成一个循环先一路向左找到最左节点然后不断通过“右指针或右线索”向后移动。线索二叉树的实际应用在现代工程里不多但它代表了一种“挖掘数据结构闲置空间”的思维方式很多追求极致内存性能的嵌入式场景还会用到类似思路。热词里提到了“嵌入式二叉树”和“线索二叉树”这两个点经常一起出现在嵌入式算法面试里因为嵌入式环境内存紧张线索化的空间节省就很实在。8. 二叉树学习中最容易踩的坑和排查经验8.1 递归深度引发的栈溢出前19天刷线性结构时很少有人担心递归深度因为题目规模通常很小。但二叉树题目里最坏情况——比如树退化成一条链——递归深度等于节点数。如果题目给的树有10万个节点递归栈很可能直接爆掉。我在一次练习中就遇到这种情况一道“求二叉树最大深度”的题测试用例里有一条10万节点的单链树递归版直接栈溢出。解决办法有两个一是把递归改成显式栈迭代二是用层序遍历求深度。从此我养成一个习惯——看到树题先看数据规模超过1万就小心递归。8.2 空指针和叶子节点的边界处理二叉树代码里最常见的运行错误就是空指针解引用。关键是养成“入口先判空”的肌肉记忆if (root nullptr) return;还有个容易被忽略的细节是“判断左孩子/右孩子是否为空”的时机。比如层序遍历里只有孩子非空才入队否则队列里会混入空指针。再比如求路径和的问题叶子节点的判断条件是root-left nullptr root-right nullptr这个条件很多人会漏掉一边。8.3 用“最小复现用例画图”定位错误我在刷二叉树题目时遇到逻辑错误从来不会直接“瞪眼找bug”而是主动构造一个最小复现用例。如果我写的“判断平衡二叉树”错了我就手动构造一棵只有3个节点的左倾树然后打印每个节点的左右子树高度。通过观察输出和手算值的差异很容易定位是哪一层递归出了问题。另一个经验是二叉树题目必须画图不画图全靠脑子想十有八九出错。就算是在电脑上刷题我也会先在草稿纸上画出树的结构、标出遍历序列再写代码。很多看起来神奇的“bug”其实都是自己对树的结构没想清楚。8.4 测试用例的“覆盖意识”二叉树题目刷多了我总结了一套必测的场景空树root nullptr单节点树只有左子树的链式树只有右子树的链式树完全二叉树有一个节点的值特别大或特别小涉及比较运算时只要你提交前把这五类用例都测一遍很多边界问题都能提前暴露。尤其是“只有左子树”和“只有右子树”这两类能把递归里左右不对称的bug逼出来。学习二叉树的第20天我的最大收获不是背会了多少个模板而是终于理解了“递归是树的自然语言”。从这一章开始后面的图、堆、并查集、线段树本质上都是用树或树的变体来建模。如果你也正学到这我的建议是不要急着刷题先把常见的树结构亲手画一遍、递归展开一遍真正把“每次递归返回什么”想清楚再上强度做题也不迟。