二叉树这个系列我已经连续刷到第九篇了。说实话，到这一步才是真正吃力的时候——前面几篇讲基础遍历、讲层序、讲路径问题，还停留在“会用模板”的阶段，但只要你稍微把题目变一变，比如告诉你先序和中序让你把树画出来，或者让你判断一棵树到底是不是搜索树，很多人就开始懵。这篇我打算把二叉树里几个最容易“似懂非懂”的考点一次串起来：深度怎么求、先中后序到底怎么确定、知道了先序和中序怎么还原整棵树、二叉搜索树的本质怎么把握，以及线索二叉树究竟在干一件什么事。不管是刚开始刷题的小白，还是准备面试想系统过一遍二叉树的老手，这些内容都能用得上。
1. 二叉树的深度：递归、迭代与易错点
1.1 最大深度：后序遍历的天然应用
先看最经典的 LeetCode 104，求二叉树最大深度。这题其实有两种理解路径，一种是从根往下数，用先序遍历记录当前深度，另一种是标准的递归后序遍历。后者在面试里更常被问到，代码简单到离谱：
int maxDepth(TreeNode* root) { if (root == nullptr) return 0; int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return max(leftDepth, rightDepth) + 1; }很多初学者会奇怪，为什么这题用后序遍历？因为“深度”这个概念，直观上是根到叶子节点的层数，递归顺序天然是自顶向下，但代码里却是先递归左右孩子，再回来处理根节点。这里的关键在于把“深度”换算成“高度”：根节点的高度，就是整棵树的最大深度。而后序遍历的特点是先处理完左右子树，才能得到左右子树的高度，然后取最大值加一，得到当前节点的高度。这就把自顶向下的“深度”问题，转换成了自底向上的“高度”问题，代码写起来最自然。
我自己刷题时有个体会：深度优先搜索的三种遍历，很多时候并不需要刻意区分用哪种，但要明白为什么后序适合这个场景。像这种需要“子树返回信息给父节点”的题目，后序几乎是唯一选择。如果硬用先序，就得额外传一个 depth 参数进去，代码也能写，但明显绕了一圈。
1.2 最小深度：最容易踩的坑
LeetCode 111，求二叉树最小深度。题目定义很清楚：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意这里有个“叶子节点”的限定，很多人没看清就写：
int minDepth(TreeNode* root) { if (root == nullptr) return 0; return min(minDepth(root->left), minDepth(root->right)) + 1; }这个写法在大多数例子上是对的，但只要遇到退化树就会出错。比如一棵树只有右子树，没有左子树：
1 \ 2 \ 3按照错误代码，root->left 返回 0，root->right 返回 2，min(0,2)+1 = 1，但正确答案应该是 3，因为根节点到最近的叶子节点，路径是 1->2->3。问题就出在 root->left == nullptr 时，不能把“没有左子树”当成“左子树高度为0”，空指针对应的节点根本不是叶子节点，不应该参与比较。
正确写法是区分左右孩子是否为空的四种情况：
int minDepth(TreeNode* root) { if (root == nullptr) return 0; if (root->left == nullptr) return minDepth(root->right) + 1; if (root->right == nullptr) return minDepth(root->left) + 1; return min(minDepth(root->left), minDepth(root->right)) + 1; }这个坑我当年踩过，面试时也见过不少候选人栽在这里。本质原因是“空子树”和“叶子节点”这两个概念被混淆了。叶子节点是左右孩子都为空的节点，空子树不属于任何路径。你把这个逻辑理清楚，代码就不会出错。
1.3 层序求深度的另类思路
深度问题除了递归，用层序遍历（BFS）也非常直观。每遍历完一层，高度加一，直到队列为空。层序解法最大的好处是可以在求最小深度时提前退出：当你第一次遇到叶子节点时，当前所在层数就是最小深度，不需要遍历完整棵树。
int minDepth(TreeNode* root) { if (root == nullptr) return 0; queue<TreeNode*> q; q.push(root); int depth = 1; while (!q.empty()) { int size = q.size(); 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); } depth++; } return depth; }如果你是先学递归再学迭代，可能会觉得层序多此一举。但从实际刷题角度看，层序求深度是后面一系列“树右下角节点”“最大宽度”“右视图”等题目的基础。同一个框架能解决一堆题，性价比很高。我建议深度的递归和迭代都要掌握，面试官有时候会特意让你用两种方式写，目的就是想看你对遍历结构的理解深不深。
2. 二叉树的遍历：先序、中序、后序怎么确定
2.1 三种遍历序列的判底方法
说到二叉树的遍历，很多人第一反应是背顺序。先序遍历是根左右，中序遍历是左根右，后序遍历是左右根。这三个名字的由来其实特别直白：你只看根节点被访问的位置。如果根节点最先被访问，就叫先序；根节点在左右子树中间，就叫中序；根节点最后被访问，就叫后序。
关键是“访问”这个概念。每到一个节点，你其实要做三件事：访问当前节点、遍历左子树、遍历右子树。到底先把哪件事做了，决定了遍历叫什么名字。我经常跟身边的朋友说，你不需要背“左根右”这种口诀，你只需要问自己：我想先处理根，还是先处理左子树？想清楚这个，所有遍历顺序都能推出来。
给一棵很简单的树手动走一遍：
1 / \ 2 3 / \ \ 4 5 6先序遍历：先访问1，然后进入左子树，访问2，进入2的左子树，访问4，再回到2的右子树访问5，然后回到根节点1的右子树，访问3，最后访问3的右孩子6。所以结果就是 1,2,4,5,3,6。
中序遍历：先进入左子树，到节点2，再进入2的左子树，访问4，回来访问2，再访问5，然后回到根节点访问1，再进入右子树，访问3的右子树先到空，再访问3，最后访问6。结果是 4,2,5,1,3,6。
后序遍历：先处理左右子树，最后处理根。结果是 4,5,2,6,3,1。
我建议你每次遇到遍历的题，都自己在纸上画一棵树，从根开始沿着路径走一遍，比背一百遍口诀都管用。特别是后序，很多人容易写成右左根，原因就是对“访问”和“遍历”的先后关系没掰扯清楚。
2.2 递归模板：只需要挪一行代码
递归版本的三种遍历，本质是同一个模板：
void traversal(TreeNode* root) { if (root == nullptr) return; // 先序：在这里访问 root traversal(root->left); // 中序：在这里访问 root traversal(root->right); // 后序：在这里访问 root }有些教程会把“访问”抽象成一个函数，比如 result.push_back(root->val)。你只需要把这一行放在不同位置，就能得到三种遍历。刚开始学我也觉得这太简单了，简单到不真实。但等你用到复杂题里，比如二叉搜索树验证、求公共祖先、序列化，你会发现递归模板真的就是整个二叉树算法的地基。
2.3 迭代遍历：统一写法，告别三个模板
递归写法虽然简洁，但面试里经常追问“如果不想用递归怎么办”。这时候就得写迭代版本。传统写法要分别用栈模拟，先序和后序还不一样，容易记混。后来我找到一个比较省脑子的统一写法，核心是用一个空指针标记“该访问当前节点了”，把递归的调用栈显式模拟出来。
以中序遍历为例：
vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; if (root) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); if (node != nullptr) { st.pop(); if (node->right) st.push(node->right); st.push(node); st.push(nullptr); if (node->left) st.push(node->left); } else { st.pop(); node = st.top(); st.pop(); res.push_back(node->val); } } return res; }原理是：当电流顶节点不是空指针时，说明当前节点还没有被“访问”，需要把它和它的子树继续拆入栈；当栈顶是空指针，说明下一个节点是之前被标记为“已处理”的节点，这时候弹出并记录。调整入栈顺序，就能写出先序和后序：
- 中序（左根右）：先压右孩子，再压当前节点，再压nullptr，最后压左孩子
- 先序（根左右）：先压右孩子，再压左孩子，再压当前节点，最后压nullptr
- 后序（左右根）：先压当前节点，再压nullptr，再压右孩子，最后压左孩子
我个人不太建议死记这个顺序，而是抓住一个点：栈是后进先出的，你希望哪个节点先被处理，就让它靠近栈顶。nullptr 的作用是告诉代码“当前节点已经处理过左右子树，现在该把值放进结果数组了”。只要把这个点理解了，三种遍历就能用一套代码写完，考试和面试都稳。
3. 知道先序和中序，确定树的样子
3.1 为什么先序+中序就能还原一棵树
这个问题在很多面试题里出现过，最开始我也觉得很神奇：树不是有很多种可能吗？为什么给了先序和中序，就能唯一确定它的结构？原因在于这两个序列提供了互补的信息。
先序序列的第一个元素一定是整棵树的根节点。这个信息是“自上而下”的定位。但只有先序，你不知道根节点的左子树有哪些节点、右子树有哪些节点。中序序列恰好能补上这个缺口：在中序序列里找到根节点的位置，它左边就是左子树的所有节点，右边就是右子树的所有节点。有了根节点，有了左右子树的节点集合，再对左右子树分别递归套用同样的逻辑，整棵树的样子就出来了。
你可能会问，为什么先序+后序不能还原呢？因为如果某个节点只有一个孩子，先序和后序得到的结果是一样的，无法判断这个孩子是左还是右，就会出现歧义。中序能提供左右子树划分的准确分界，所以“先序或后序 + 中序”才是还原二叉树的黄金组合。
3.2 LeetCode 105：用先序和中序建树
题目是 LeetCode 105，要求根据一棵树的前序遍历与中序遍历构造二叉树。核心思路是中序序列中找到根的位置，计算左子树大小，然后用这个大小去切割先序序列。
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 pl, int pr, vector<int>& in, int il, int ir, unordered_map<int, int>& pos) { if (pl > pr || il > ir) return nullptr; int rootVal = pre[pl]; TreeNode* root = new TreeNode(rootVal); int rootIndex = pos[rootVal]; int leftSize = rootIndex - il; root->left = build(pre, pl + 1, pl + leftSize, in, il, rootIndex - 1, pos); root->right = build(pre, pl + leftSize + 1, pr, in, rootIndex + 1, ir, pos); return root; }这里最关键的是 leftSize 的计算。你会发现中序序列的根位置减去中序左边界，就是左子树的节点个数。先序序列里，根节点之后紧跟着的是完整的左子树序列，长度为 leftSize，再往后才是右子树序列。所以递归参数里，左子树的先序范围是 [pl+1, pl+leftSize]，右子树是 [pl+leftSize+1, pr]。
我刚开始写这题时，总爱在边界上纠结，后来总结了一个经验：不要凭记忆写边界，而是每次递归时想清楚“我当前知道的左右子树节点范围是什么”，把范围画出来再填数字。
3.3 变体：中序+后序怎么建树
同样的逻辑，换成中序和后序也能建树。只不过根节点变成了后序序列的最后一个元素。其他步骤几乎一模一样：在中序里找根的位置，计算左子树大小，再切割中序和后序序列进行递归。
TreeNode* buildTreeFromInPost(vector<int>& inorder, vector<int>& postorder) { unordered_map<int, int> pos; for (int i = 0; i < inorder.size(); i++) { pos[inorder[i]] = i; } return build(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, pos); } TreeNode* build(vector<int>& in, int il, int ir, vector<int>& post, int pl, int pr, unordered_map<int, int>& pos) { if (il > ir || pl > pr) return nullptr; int rootVal = post[pr]; TreeNode* root = new TreeNode(rootVal); int rootIndex = pos[rootVal]; int leftSize = rootIndex - il; root->left = build(in, il, rootIndex - 1, post, pl, pl + leftSize - 1, pos); root->right = build(in, rootIndex + 1, ir, post, pl + leftSize, pr - 1, pos); return root; }你如果看懂了 LeetCode 105，这只算一个小的逻辑迁移。面试中出现“用后序和中序重建二叉树”的变体题，大概率是想考察你会不会举一反三。建议把这两题一起刷，互相比较一下边界怎么变化，比单独刷十题都有效。
4. 二叉搜索树：有序结构与验证
4.1 二叉搜索树的定义与核心性质
二叉搜索树（BST）的定义看起来简单：左子树所有节点的值小于根节点，右子树所有节点的值大于根节点，并且左右子树也都是二叉搜索树。但真正用起来，很多人会忽略“所有节点”这四个字。
BST 最重要的性质是：中序遍历结果是一个严格递增的序列。这个性质几乎是所有 BST 题目的题眼。比如求第 K 小元素，就是中序遍历到第 K 个节点；验证一棵树是不是 BST，就是看中序遍历是否严格递增；找 BST 中两个节点的最近公共祖先，也可以利用中序或者递归判断大小。可以说理解了中序递增，BST 就掌握了一大半。
4.2 验证 BST：LeetCode 98 的经典陷阱
LeetCode 98 是验证一棵树是不是二叉搜索树。很多人第一次写的代码是这样的：
bool isValidBST(TreeNode* root) { if (root == nullptr) return true; if (root->left && root->left->val >= root->val) return false; if (root->right && root->right->val <= root->val) return false; return isValidBST(root->left) && isValidBST(root->right); }这个代码在简单用例上看着没问题，但遇到下面这棵树就挂了：
5 / \ 1 6 / \ 4 7按照上面的写法，节点6的右子树7>6没问题，节点6的左子树4<6也没问题，但4是节点5的右子树的左孩子，它实际上小于5，违反了“右子树所有节点的值大于根节点”的定义。问题就出在只比较了局部父子关系，没有把祖先节点的范围约束传递下去。
正确的做法是使用区间传递法，让每个节点都处于一个开区间内：向左走时更新上界为父节点值，向右走时更新下界为父节点值。用 C++ 的话，初始上下界可以用 LONG_MIN 和 LONG_MAX 来避免 int 边界干扰，因为题目里节点值本身是 int 范围内的。
bool isValidBST(TreeNode* root) { return check(root, LONG_MIN, LONG_MAX); } bool check(TreeNode* node, long low, long high) { if (node == nullptr) return true; if (node->val <= low || node->val >= high) return false; return check(node->left, low, node->val) && check(node->right, node->val, high); }这里有一个细节：我用的是开区间，因为 BST 不允许相等值。如果题目允许重复，就要想清楚等号的边界应该放哪一边。更常见的做法是干脆用中序遍历，因为 BST 中序严格递增，任何前一个值 >= 当前值都说明不是 BST：
bool isValidBST(TreeNode* root) { long pre = LONG_MIN; return inorder(root, pre); } bool inorder(TreeNode* node, long& pre) { if (node == nullptr) return true; if (!inorder(node->left, pre)) return false; if (node->val <= pre) return false; pre = node->val; return inorder(node->right, pre); }两种方法都建议熟练掌握。区间法对空间复杂度的控制更直观，中序法在解决“第K小元素”这类问题上更有扩展性。我面试时更倾向于先说中序法，因为思路清晰，不容易被追问边界。
4.3 BST 的基本操作：插入、删除、查找
二叉搜索树的查找很简单，根据目标值和当前节点值的大小，决定向左还是向右走，直到找到或者走到空。插入也是类似，递归找到空位后创建新节点。真正麻烦的是删除节点。
删除一个节点分三种情况：
- 节点没有孩子，直接删掉，返回空指针。
- 节点只有一个孩子，用这个孩子替代被删除节点。
- 节点有两个孩子，这时候需要找到右子树中最小的节点（或者左子树中最大的节点）来接替被删除节点，再删除那个最小节点。
这里的关键是为什么两个孩子的节点要用右子树最小值替换？因为要维持 BST 性质，替换节点必须大于左子树所有值，小于右子树所有值。右子树的最小节点正好满足：它大于左子树的全部节点，同时小于右子树的其他所有节点，用它来替换，树依然是 BST。
代码虽然长，但只要理解了三种情况，它就是一道“先找再删”的模拟题，没什么难度。LeetCode 450 就是专门针对删除操作的，建议做一遍。
5. 线索二叉树：隐形的前驱后继指针
5.1 什么是线索二叉树
前面提到了一个概念：一棵有 n 个节点的二叉树，实际上有 n+1 个空指针域。因为每个节点有左右两个指针，总共 2n 个指针，非空指针是 n-1 个，所以空指针是 2n - (n-1) = n+1 个。线索二叉树想干的事情，就是把这些空指针利用起来，让它指向遍历过程中的前驱节点或者后继节点。
根据遍历方式不同，线索二叉树可以分为先序线索二叉树、中序线索二叉树和后序线索二叉树。以中序线索二叉树为例：如果一个节点的左孩子为空，就让它的 left 指针指向中序遍历中的前驱节点；如果一个节点的右孩子为空，就让它的 right 指针指向中序遍历中的后继节点。
这样一来，树里的每一个空指针就不再是单纯的“空占位”，而是保存了遍历顺序信息，所以叫“线索”。
5.2 中序线索化的构建过程
线索化不是另建一棵树，而是在原有二叉树上做修改。核心依旧是一次中序遍历，在访问节点的时候，同时处理当前节点和上一个被访问节点之间的线索关系。
写一段线索化的核心代码，这里的 pre 要在递归外层维护，它是中序遍历序列中当前节点的前驱：
void inorderThread(TreeNode* root, TreeNode* &pre) { if (root == nullptr) return; inorderThread(root->left, pre); if (root->left == nullptr) { root->left = pre; root->ltag = 1; // 1表示指针是前驱线索 } if (pre != nullptr && pre->right == nullptr) { pre->right = root; pre->rtag = 1; // 1表示指针是后继线索 } pre = root; inorderThread(root->right, pre); }注意这段代码里的 pre 不是局部变量，它需要在递归过程中一直指向“刚刚访问过的那个节点”。每次访问完当前节点，马上把 pre 指向当前节点，下一个节点就能利用它建立前驱线索。你在脑子过一遍流程就会明白：中序遍历顺序是左根右，所以访问当前节点时，左子树已经全部遍历完，当前节点的前驱就是左子树里最后被访问的节点，正好是上一轮的 pre。而当前节点又是右子树的“前驱”，需要在访问右子树前，把当前节点的右孩子为空的情况处理掉。
这里有个容易混淆的点：ltag 和 rtag 的用途。它们不是存访问时间，而是用来区分节点的 left 指针到底是指向左孩子，还是指向前驱线索。如果不加这个标记，遍历时就会陷入死循环，分不清一个节点是原有子树还是线索指针。
5.3 线索二叉树的实际应用场景
你可能觉得这个东西有点过时，毕竟现代工程里很少有人真的去建一棵线索二叉树。但它的思想却无处不在。
最典型的例子是 Morris 遍历。Morris 遍历可以在不使用递归栈和额外空间的情况下，完成二叉树的中序遍历。它利用叶子节点的空指针，临时把当前节点指向前驱节点，遍历完以后再恢复树的结构。这和线索二叉树的本质是一模一样的，只是线索二叉树把线索长留在了树上，而 Morris 遍历是“用完即走”。
另一个实际场景是高频次的前驱后继查询。如果你需要在很短的时间内反复找某个节点的中序前驱或后继，线索化之后，这些操作都是 O(1) 复杂度，不需要每次从根节点重新遍历。数据库索引、区间查询这些底层的树结构搜索，有时候会用到类似的思路来加速节点的邻接访问。
你在面试时如果被问到“线索二叉树有什么用”，可以从“利用空指针避免递归栈消耗”和“加速前驱后继查找”两个角度回答，然后再提一句 Morris 遍历就是其思想的一种实践，会显得你理解比较深。
5.4 “线索”和“普通遍历”怎么选
普通二叉树遍历靠递归或显式栈，代码好写，逻辑直观，但需要额外空间。线索二叉树遍历时不需要栈，可以按线索一路找下去，但维护线索比较麻烦，插入和删除节点时的成本很高。
所以实际选型很清晰地遵循一条原则：需要频繁遍历、频繁查前驱后继、且树结构不太变动，线索化是划算的；树经常增删节点，就别用线索，老老实实写递归。
我自己刷题时不会刻意去实现复杂动态线索化，但我会把 Morris 遍历当作对二叉树空间复杂度理解的试金石。能在纸上把 Morris 中序遍历的整个过程画出来的人，对树的指针操作理解基本已经到位了。建议你有时间可以自己模拟一遍。
最后再分享一点个人经验。二叉树这个模块，最忌“只刷题不画图”。我每次遇到遍历、重建、线索化这类题，都会先在草稿纸上画一棵树，再手动写出先序、中序、后序的序列，然后再去对照代码。这个习惯看着费时间，但实际上是把递归调用、栈的变化、线索指向这些抽象概念全部可视化。刷到后面你会发现，绝大多数树相关的难题，归根结底都在变着法地考察“遍历”两个字。深度问题是后序，验证 BST 是中序，重建二叉树是先序加中序，线索二叉树是中序的变体。把这些主线的顺序捋顺了，二叉树这一整块就算真正过了关。
