【数据结构与算法】二叉树做题做题做题

1.

洛谷 P4913 二叉树深度（递归写法详细解析）

这道题本质就是一个非常经典的二叉树问题；给你一棵树的结构，让你求从根节点到最远叶子节点的最大层数，也就是我们常说的“树的深度”。

题目中给出的输入其实已经帮我们把树“存好了”；每个节点 i 都会告诉你它的左孩子和右孩子是谁，如果是 0 就说明没有孩子；并且根节点固定为 1，所以我们只需要从 1 出发，一层一层往下算即可。

这类题最直接、最符合直觉的方法就是递归；因为树本身就是一种递归结构——一个节点的深度，取决于它左右子树的深度；所以思路可以很自然地写成：当前节点的深度 = 左子树深度 和 右子树深度 的最大值 + 1。

对应到代码就是这样一段核心函数：

int getdepth(int node) { if (node == 0) return 0; int leftdepth = getdepth(leftchild[node]); int rightdepth = getdepth(rightchild[node]); return max(leftdepth, rightdepth) + 1; }

这里有几个细节是必须理解的；首先为什么 node == 0 要返回 0；因为 0 表示这个节点不存在，也就是空树，而空树的深度就是 0；其次为什么最后要 +1；因为当前这个节点本身也要算一层，比如一个叶子节点，它左右都是 0，那么深度就是 max(0,0)+1 = 1；再一个就是为什么要取 max；因为题目要求的是“最大深度”，也就是走最远的那一条路径。

整道题的数据规模最大可以到 10^6；所以我们用数组来存储树结构是非常合理的；leftchild[i] 表示 i 的左孩子；rightchild[i] 表示右孩子；这样查找是 O(1)，整体效率很高。

完整代码如下，可以直接运行：

#include<iostream> using namespace std; const int MAXN = 1e6 + 5; int leftchild[MAXN]; int rightchild[MAXN]; int n; int getdepth(int node) { if (node == 0) return 0; int leftdepth = getdepth(leftchild[node]); int rightdepth = getdepth(rightchild[node]); return max(leftdepth, rightdepth) + 1; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> leftchild[i] >> rightchild[i]; } int ans = getdepth(1); cout << ans; return 0; }

这段代码的执行过程其实可以理解为“从根节点一路往下探”；每走到一个节点，就继续往它的左右孩子递归；直到走到叶子节点，再一层一层返回；在返回的过程中不断取最大值；最终得到整棵树的最大深度。

时间复杂度是 O(n)；因为每个节点只访问一次；空间复杂度主要来自递归栈，在最坏情况下（树退化成一条链）会达到 O(n)；也就是说如果数据非常极端，是有可能出现栈溢出的；不过在大多数正常数据下是没问题的；

递归过程图解（一定要搞懂这一部分）

很多人写这道题的时候，其实代码会写，但对递归是“怎么跑的”并不清楚；这一段我用一棵简单的树，把整个过程一步一步讲清楚。

我们用下面这棵树来演示：

1 / \ 2 7 / \ 3 6 / 4

我们调用的是：

getdepth(1);

程序一开始不会直接算出答案，而是会先去“问子节点”；也就是说它会先去算左子树，再算右子树，可以理解为：

getdepth(1) ├── getdepth(2) └── getdepth(7)

接下来程序会优先一直往左走，也就是不断递归下去：

getdepth(2) ├── getdepth(3) └── getdepth(6) getdepth(3) ├── getdepth(4) └── getdepth(0) getdepth(4) ├── getdepth(0) └── getdepth(0)

注意这里已经走到最底部了；节点 4 的左右孩子都是 0，说明它是叶子节点；这时候递归不能再往下了，就开始“返回结果”。

首先返回的是节点 4：

getdepth(4) = max(0, 0) + 1 = 1

然后把结果带回给上一层，也就是节点 3：

getdepth(3) = max(1, 0) + 1 = 2

接着处理节点 6（它是叶子节点）：

getdepth(6) = max(0, 0) + 1 = 1

再回到节点 2：

getdepth(2) = max(2, 1) + 1 = 3

左子树算完之后，程序才会去算右子树，也就是节点 7：

getdepth(7) = max(0, 0) + 1 = 1

最后回到根节点 1，整棵树的答案也就出来了：

getdepth(1) = max(3, 1) + 1 = 4

整个过程如果用一句话总结就是：

先一路往下递归，把问题不断拆小；再从最底层开始一层一层返回结果；最终在根节点得到答案。

很多人容易误以为递归是在“从上往下算”，其实不是；真正的计算发生在“回来的时候”，也就是从叶子节点开始往上合并结果；这就是递归在树问题中的核心思想。

2.

洛谷 P1305 新二叉树（前序遍历 + 递归详解）

这道题本质就是二叉树的基础操作；给你一棵用字符表示的二叉树结构，让你输出它的前序遍历结果；相比普通数组建树，这道题的特点是用字符作为节点，并且用*表示空节点。

题目输入的每一行其实就是在描述一棵树的“父子关系”；第一个字符是当前节点，后两个字符分别是它的左孩子和右孩子；比如abc就表示 a 的左孩子是 b，右孩子是 c；如果是d**，说明 d 是叶子节点。

这里我们用unordered_map<char, pair<char, char>>来存树结构；意思就是：通过一个节点，可以快速找到它的左右孩子；这种写法比数组更灵活，也更适合字符节点的题目。

整道题的核心其实就是“前序遍历”；所谓前序遍历，就是：

先访问当前节点；再访问左子树；最后访问右子树。

对应的递归写法非常简单，也非常经典：

void preorder(char node) { if (node == '*') { return; } cout << node; preorder(tree[node].first); preorder(tree[node].second); }

这里有两个关键点需要注意；第一，为什么遇到*要直接 return；因为*表示空节点，相当于不存在；第二，访问顺序一定是：当前节点 → 左子树 → 右子树，这个顺序一旦写错，结果就完全不一样。

程序的执行过程其实和你上一题“求深度”的递归非常像；也是先一路往下递归，再一层一层返回；只不过这次不是“计算值”，而是“输出路径”。

我们用样例简单走一遍：

abc bdi cj* d** i** j**

这棵树结构大概是：

a / \ b c / \ \ d i j

递归调用过程可以理解为：

先从 a 开始；输出 a；然后进入左子树 b；输出 b；继续进入 d；输出 d；发现 d 没有孩子就返回；再回到 b，进入 i；输出 i；再返回到 a；进入右子树 c；输出 c；最后输出 j。

所以最终输出就是：

abdicj

完整代码如下，可以直接运行：

#include<iostream> #include<unordered_map> using namespace std; int n; unordered_map<char, pair<char, char>> tree; void preorder(char node) { if (node == '*') { return; } cout << node; preorder(tree[node].first); preorder(tree[node].second); } int main() { cin >> n; char root; for (int i = 1; i <= n; i++) { char parent, left, right; cin >> parent >> left >> right; tree[parent] = { left, right }; if (i == 1) { root = parent; } } preorder(root); return 0; }

时间复杂度是 O(n)；因为每个节点只访问一次；空间复杂度主要来自递归调用栈，最坏情况下是 O(n)。

这道题其实是“树遍历”的入门题；掌握之后，你可以顺带学习另外两种遍历方式：中序遍历和后序遍历；它们的区别本质就是“访问当前节点的位置不同”；一旦理解递归，这三种写法都是一行改一行的事情。

最后总结一句话：前序遍历就是“先自己，再左，再右”；只要记住这个顺序，这类题基本不会出错。

3.

#include<iostream> using namespace std; void getpreorder(string inorder, string postorder) { if (inorder.empty()) return; char root = postorder.back(); cout << root; int rootpos = inorder.find(root); string leftinorder = inorder.substr(0, rootpos); string leftpostorder = postorder.substr(0,leftinorder.size()); getpreorder(leftinorder, leftpostorder); string rightinorder = inorder.substr(rootpos + 1); string rightpostorder = postorder.substr(leftinorder.size(),rightinorder.size()); getpreorder(rightinorder, rightpostorder); } int main() { string inorder, postorder; cin >> inorder >> postorder; getpreorder(inorder, postorder); return 0; }

洛谷 P1030 求先序排列（中序 + 后序 推前序详解）

这道题是二叉树里一个非常经典的“反推问题”；已知中序遍历和后序遍历，让你还原出先序遍历；节点数量不大（≤8），但思路非常重要，是树这一块的核心知识之一。

先说结论，这题本质就一句话：后序确定根；中序划分左右；递归构建。

我们先快速回顾三种遍历的特点；前序是“根 → 左 → 右”；中序是“左 → 根 → 右”；后序是“左 → 右 → 根”；这里最关键的是：后序遍历的最后一个节点一定是整棵树的根。

比如样例：

中序：BADC 后序：BDCA

后序最后一个字符是 A；所以 A 一定是整棵树的根节点。

接下来我们去中序序列里找 A；可以把中序分成两部分：

中序： B | A | DC ↑ 根

左边B是左子树；右边DC是右子树；这一步非常关键，相当于把树“切开了”。

接下来要做的是：在后序序列中，把左右子树对应的部分也切出来；因为后序是“左 → 右 → 根”，所以去掉最后一个 A 后：

后序：BDC

前面一部分是左子树，后面一部分是右子树；左子树有几个节点？看中序左边的长度；这里左边是B，长度是 1，所以：

左子树后序：B 右子树后序：DC

这样一来，我们就把问题拆成了两个子问题；接下来对左右子树继续做同样的事情；这就是递归。

你的代码正是按照这个思路写的：

void getpreorder(string inorder, string postorder) { if (inorder.empty()) return; char root = postorder.back(); // 后序最后一个是根 cout << root; int rootpos = inorder.find(root); string leftinorder = inorder.substr(0, rootpos); string leftpostorder = postorder.substr(0, leftinorder.size()); getpreorder(leftinorder, leftpostorder); string rightinorder = inorder.substr(rootpos + 1); string rightpostorder = postorder.substr(leftinorder.size(), rightinorder.size()); getpreorder(rightinorder, rightpostorder); }

这里每一步其实都对应一个明确的含义；postorder.back() 找根；find(root) 在中序里定位；substr 切出左右子树；然后递归处理。

我们把整个过程完整走一遍，会更清楚。

第一步：确定根节点
后序最后一个是 A；输出 A。

第二步：划分中序
B | A | DC；左子树是 B；右子树是 DC。

第三步：划分后序
去掉 A 后是 BDC；左子树长度是 1；所以左是 B；右是 DC。

第四步：递归左子树
中序：B；后序：B；根是 B；输出 B。

第五步：递归右子树
中序：DC；后序：DC；根是 C；输出 C；再继续拆：

中序：D | C 后序：D | C

根是 C；左子树是 D；继续递归输出 D。

最终输出顺序是：

A B C D

也就是：

ABCD

这正是先序遍历（根 → 左 → 右）。

整个过程你可以这样理解：我们不是在“构建整棵树”，而是在“边拆边输出”；利用遍历的性质，一步一步把结构还原出来。

时间复杂度是 O(n^2)；因为每次 find 都要线性查找；但 n 很小，所以完全没问题；如果数据更大，可以用哈希表优化到 O(n)。

最后总结一句话：后序找根；中序分树；递归处理；输出顺序就是先序。