算法学习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; queue<TreeNode*> 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 递归与迭代：两种实现怎么选
面试里常要求你“不要用递归实现遍历”，这时候你要会用显式栈模拟递归。以中序遍历为例，迭代写法的思路是：先沿左子树一路压栈，到底后弹栈访问节点，再转向右子树。
vector<int> inorderTraversal(TreeNode* root) { vector<int> res; 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(); 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(vector<int>& preorder, vector<int>& inorder) { unordered_map<int, 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(vector<int>& pre, int preL, int preR, vector<int>& in, int inL, int inR, unordered_map<int, 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的左孩子是k2，k2的右孩子是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个指向实际节点，剩下n+1个都是空指针。线索化就是把这些空指针利用起来，让它们指向遍历序列中的“前驱”或“后继”节点，这样遍历时就不需要递归或栈了。
线索二叉树在教科书里看起来有点“绕”，但实际写一遍线索化过程，反而比想象中简单。
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天，我的最大收获不是背会了多少个模板，而是终于理解了“递归是树的自然语言”。从这一章开始，后面的图、堆、并查集、线段树，本质上都是用树或树的变体来建模。如果你也正学到这，我的建议是：不要急着刷题，先把常见的树结构亲手画一遍、递归展开一遍，真正把“每次递归返回什么”想清楚，再上强度做题也不迟。
