企业官网建设流程全解析

我不会起名字322· 后端 / 算法 / 数据库

📘 技术栈 ｜ 🧩 力扣 Hot100 ｜ 🐹 Go 项目 ｜ 🟥 Redis ｜ 🐬 MySQL

二叉树核心知识一次讲透：递归序视角下的遍历、还原树与二叉搜索树

学二叉树时最容易卡住的地方，往往不是代码写不出来，而是脑子里的模型是散的：前序、中序、后序三个名字背得很熟，可一旦题目换成「已知前序和中序，还原这棵树」就无从下手；等到二叉搜索树的删除节点又要分三种情况，每次都得现场推一遍。

问题出在把这三者当成了三个独立知识点。其实它们只是同一件事的不同观察角度。这篇文章用一棵示例树把它们串起来，讲完你应该能自己推导出任意一颗树的遍历结果、手写三种迭代写法、从遍历序列还原出树，并且独立完成二叉搜索树的增删查。

一、先建一棵示例树

后面所有推导都基于这棵树，建议先记牢它的形状：

8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13

这是一棵合法的二叉搜索树，本文的四种遍历结果分别是：

注意中序结果是升序的——这不是巧合，后面讲二叉搜索树时会解释。

二、递归序：三种遍历其实是同一件事

递归遍历的代码极其相似，区别只在 printf 的位置：

voidtraverse(TreeNode*root){if(root==nullptr)return;// ① 第一次来到这个节点traverse(root->left);// ② 第二次来到这个节点traverse(root->right);// ③ 第三次来到这个节点}

关键认知：在递归过程中，每个节点都会被「经过」三次。前序就是第 ① 次经过时记录，中序是第 ② 次，后序是第 ③ 次。

所以三种遍历写出来只差一行：

// 前序：根 左 右voidpreorder(TreeNode*root,vector<int>&out){if(!root)return;out.push_back(root->val);// ①preorder(root->left,out);preorder(root->right,out);}// 中序：左 根 右voidinorder(TreeNode*root,vector<int>&out){if(!root)return;inorder(root->left,out);out.push_back(root->val);// ②inorder(root->right,out);}// 后序：左 右 根voidpostorder(TreeNode*root,vector<int>&out){if(!root)return;postorder(root->left,out);postorder(root->right,out);out.push_back(root->val);// ③}

一旦建立「递归序」这个模型，就不需要再死记硬背顺序，遇到变形题（比如「第 k 个被访问的节点是谁」）也能直接推导。

复杂度：三种递归遍历都是 O(n) 时间——每个节点恰好访问一次；空间 O(h)，h 是树高，来自递归调用栈。

三、三种迭代写法与层序 BFS

递归虽好，但树很深时会爆栈，面试也常要求手写迭代版。核心思路都是用栈模拟递归的调用过程。

前序遍历（栈）

前序最简单：栈是后进先出，所以先压右孩子、再压左孩子，弹出顺序自然就是「根→左→右」。

vector<int>preorderIter(TreeNode*root){vector<int>out;if(!root)returnout;stack<TreeNode*>st;st.push(root);while(!st.empty()){TreeNode*cur=st.top();st.pop();out.push_back(cur->val);if(cur->right)st.push(cur->right);// 右先入栈，后出if(cur->left)st.push(cur->left);}returnout;}

中序遍历（栈 + 指针）

中序要先把整条左链压进栈，弹出来时再转向右子树：

vector<int>inorderIter(TreeNode*root){vector<int>out;stack<TreeNode*>st;TreeNode*cur=root;while(cur||!st.empty()){while(cur){// 一路向左，把路径全部入栈st.push(cur);cur=cur->left;}cur=st.top();st.pop();// 左走到头，弹出并访问out.push_back(cur->val);cur=cur->right;// 转向右子树}returnout;}

后序遍历（单栈 + 前驱指针）

后序最绕。用「上一次访问的节点」判断右子树是否已经处理完：

vector<int>postorderIter(TreeNode*root){vector<int>out;stack<TreeNode*>st;TreeNode*cur=root;TreeNode*lastVisited=nullptr;while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}TreeNode*peek=st.top();// 右子树存在且还没处理过，先转过去if(peek->right&&lastVisited!=peek->right){cur=peek->right;}else{out.push_back(peek->val);lastVisited=peek;st.pop();}}returnout;}

判断条件lastVisited != peek->right是这段代码的灵魂：如果右孩子刚被访问过，说明左右都完成了，现在才能访问根。

层序遍历（队列 BFS）

层序不用栈，用队列，按层从左到右：

vector<vector<int>>levelOrder(TreeNode*root){vector<vector<int>>res;if(!root)returnres;queue<TreeNode*>q;q.push(root);while(!q.empty()){intsize=q.size();// 当前层的节点数，必须提前固定vector<int>level;for(inti=0;i<size;i++){TreeNode*cur=q.front();q.pop();level.push_back(cur->val);if(cur->left)q.push(cur->left);if(cur->right)q.push(cur->right);}res.push_back(level);}returnres;}

那个int size = q.size()是分层输出的关键——循环开始时队列里恰好是一整层的节点，必须先把这个数量锁住，否则会把下一层的节点也混进来。

四、由前序 + 中序还原一棵树

这是经典题型。抓住两条性质：

• 前序的第一个元素一定是根节点；
• 找到根在中序里的位置，它左边是左子树的所有节点，右边是右子树的所有节点。

以本文的树为例，前序8 3 1 6 4 7 10 14 13中 8 是根；8 在中序1 3 4 6 7 | 8 | 10 13 14里位于第 6 位，于是左子树有 5 个节点、右子树有 3 个。递归下去即可还原。

朴素做法每步都要在中序里线性查找根的位置，最坏（退化成链表）是 O(n²)。优化方法是先把中序的「值 → 下标」存进哈希表，查找降到 O(1)：

unordered_map<int,int>pos;// 值 -> 中序下标TreeNode*build(vector<int>&pre,intpreL,intpreR,intinL){if(preL>preR)returnnullptr;introotVal=pre[preL];// 前序首位即根intk=pos[rootVal]-inL;// 左子树节点个数TreeNode*root=newTreeNode(rootVal);root->left=build(pre,preL+1,preL+k,inL);root->right=build(pre,preL+k+1,preR,inL+k+1);returnroot;}TreeNode*buildTree(vector<int>&pre,vector<int>&in){for(inti=0;i<in.size();i++)pos[in[i]]=i;returnbuild(pre,0,pre.size()-1,0);}

加了这个哈希表后，整体复杂度从 O(n²) 降到O(n)。

注意：只有前序+中序、后序+中序才能唯一还原一棵树；前序+后序不行（无法区分左右子树）。

五、二叉搜索树（BST）

定义与核心性质

二叉搜索树满足：对任意节点，左子树所有节点值 < 该节点值 < 右子树所有节点值，且左右子树自身也是 BST。

由此得到一个高频结论：BST 的中序遍历序列是升序的。因为中序按「左→根→右」访问，而 BST 天然满足左 < 根 < 右。本文示例树的中序1 3 4 6 7 8 10 13 14正是升序。这个性质可以直接用来求「BST 的最小绝对差」「第 k 小的元素」等问题。

查找

从根开始，比当前节点小就往左、大就往右：

TreeNode*search(TreeNode*root,inttarget){TreeNode*cur=root;while(cur){if(cur->val==target)returncur;cur=(target<cur->val)?cur->left:cur->right;}returnnullptr;// 走到空，说明不存在}

每轮排除一半，本质是二分查找。

插入

先按查找的路径走到空位，再挂上去。BST 不允许重复值，遇到相等直接返回：

TreeNode*insert(TreeNode*root,intval){if(!root)returnnewTreeNode(val);TreeNode*cur=root;while(true){if(val==cur->val)returnroot;// 已存在，不插入if(val<cur->val){if(!cur->left){cur->left=newTreeNode(val);break;}cur=cur->left;}else{if(!cur->right){cur->right=newTreeNode(val);break;}cur=cur->right;}}returnroot;}

删除：三种情况

删除要保证删完之后 BST 性质依然成立，按待删节点的子节点数量分三种情况：

第三种情况是关键：不能直接删（两个孩子没地方放），只能用「继承者」的值覆盖，把问题转化成删除继承者——而继承者最多只有一个子节点，就回到了前两种情况。

TreeNode*deleteNode(TreeNode*root,intkey){if(!root)returnnullptr;if(key<root->val){root->left=deleteNode(root->left,key);}elseif(key>root->val){root->right=deleteNode(root->right,key);}else{if(!root->left)returnroot->right;// 0 或 1 个（右）if(!root->right)returnroot->left;// 1 个（左）// 两个子节点：找右子树最小节点TreeNode*succ=root->right;while(succ->left)succ=succ->left;root->val=succ->val;// 值覆盖root->right=deleteNode(root->right,succ->val);// 递归删继承者}returnroot;}

验证 BST 的经典陷阱

一个高频错误写法是「只比较当前节点和左右孩子」：

// 错误：只比较父子，会漏掉跨层约束boolbad(TreeNode*r){if(!r)returntrue;if(r->left&&r->left->val>=r->val)returnfalse;if(r->right&&r->right->val<=r->val)returnfalse;returnbad(r->left)&&bad(r->right);}

反例：根节点 8，左孩子 3，而 3 的右孩子是 9。每个父子关系都满足，但 9 出现在了左子树里，违反 BST 定义。

正确做法是给每个节点传递允许的取值区间，递归时不断收紧：

boolcheck(TreeNode*r,longlo,longhi){if(!r)returntrue;if(r->val<=lo||r->val>=hi)returnfalse;// 越界即非法returncheck(r->left,lo,r->val)&&check(r->right,r->val,hi);}boolisValidBST(TreeNode*root){returncheck(root,LONG_MIN,LONG_MAX);}

用long是为了避开节点值恰好等于INT_MIN/INT_MAX时判断失效。

六、复杂度对比与退化分析

BST 的价值在于把查找、插入、删除都压到树的高度级别：

但这个O(log n)是有前提的：树必须平衡。

如果按 1、2、3、4、5 的顺序连续插入，BST 会一路向右生长，退化成一条链表，树高变成 n，所有操作退化到O(n)。这是 BST 最大的隐患。

解决办法是引入自平衡机制——插入删除后自动调整形态，保证树高始终是对数量级。AVL 树、红黑树就是这类结构，Java 的TreeMap、C++ 的std::map底层用的正是红黑树。

另外注意，BST 不一定是完全二叉树，所以不适合用数组存储，一般用链表实现节点。只有在「高频插入、低频查找删除」的场景下，数组才可能比 BST 更划算。

七、小结

把这几条串起来，二叉树的核心就通了：

1. 三种递归遍历是同一个递归序的第 ①②③ 次访问，不用分开死记；
2. 迭代写法用栈模拟递归，层序用队列并锁住每层大小；
3. 还原树必须前序+中序或后序+中序，用哈希表把查找优化到 O(n)；
4. BST 的中序是升序，这是它所有性质的基础；
5. 删除节点按子节点个数 0/1/2分情况，两个孩子时找中序后继或前继；
6. 验证 BST 要传递上下界，只比父子会漏掉跨层约束；
7. BST 的 O(log n) 依赖平衡，退化成链表就变 O(n)，这也是 AVL / 红黑树存在的理由。