深搜的相关的知识

想象有一棵树：

这5个点我们就给它们编号：1, 2, 3, 4, 5。
编号相当于“身份证号”，每个节点都有一个独一无二的号码。

二、我们要干的事

我们要告诉电脑：

每个节点有哪些孩子；
然后从根（1号）出发，去深搜所有节点。

三、先造存储结构（这部分最关键）

在C++里，我们用一个邻接表（adjacency list）表示“谁连着谁”。

定义：

1 2	const int N = 100; // 最多100个节点 vector<int> tree[N]; // 每个节点的孩子列表

解释：

tree[1] 是一个数组，里面放着“1的孩子”；
tree[2] 是“2的孩子”；
以此类推。

四、把上面的树存进去

根据图：

1 2	1 -> 2, 3 3 -> 4, 5

所以我们写：

tree[1].push_back(2);
tree[1].push_back(3);
tree[3].push_back(4);
tree[3].push_back(5);

现在内存里相当于：

tree[1] = [2, 3]
tree[2] = []
tree[3] = [4, 5]
tree[4] = []
tree[5] = []

五、写 DFS 函数（核心！）

void dfs(int u) {
    cout << u << " ";             // 访问当前节点
    for (int v : tree[u]) {       // 遍历当前节点的孩子
        dfs(v);                   // 深度优先地访问
    }
}

解释成日常语言：

“我现在在节点u，我先打印自己。
然后看看我的每个孩子v，挨个去访问。
每次都走到底，再回来。”

六、主函数完整代码

把上面都拼起来：

#include <bits/stdc++.h>
using namespace std;

const int N = 100;
vector<int> tree[N]; // 存树结构

void dfs(int u) {
    cout << u << " ";             // 打印当前节点
    for (int v : tree[u]) {       // 遍历孩子
        dfs(v);                   // 深入孩子
    }
}

int main() {
    // 建树
    tree[1].push_back(2);
    tree[1].push_back(3);
    tree[3].push_back(4);
    tree[3].push_back(5);

    // 从1号节点开始深搜
    dfs(1);
    return 0;
}

输出结果：

1 2 3 4 5

访问顺序：
1 → 2（到头）→ 回来 → 3 → 4 → 回来 → 5

完美的深搜逻辑！

七、要理解的关键点

概念	傻瓜理解
`vector<int> tree[N];`	N个小盒子，每个盒子装当前节点的孩子编号
`push_back(x)`	把编号x放进这个节点的孩子列表
`dfs(u)`	看自己 → 递归去找所有孩子
递归	程序会“自己调用自己”，走到底再回来
没有指针	因为我们用编号连关系，电脑自己能找得到孩子

关于深搜的核心写法的疑惑:

一、先看原句

1
2
3

for (int v : tree[u]) {
    dfs(v);
}

它的作用是：

遍历当前节点 u 的所有孩子节点（存在 tree[u] 这个列表里），
对每个孩子 v 都递归调用 dfs(v)，去继续往下搜。

二、先解释 `tree[u]`

在数组版树结构里：

1	vector<int> tree[N];

tree 是一个“数组”，它里面的每个元素都是一个“孩子列表”。

举个例子（刚才那棵树）：

1
2
3

tree[1] = [2, 3]
tree[2] = []
tree[3] = [4, 5]

这意思就是：

1 号节点有孩子 2、3
2 没孩子
3 的孩子是 4、5

所以 tree[u] 就是“u号节点的所有孩子”。

三、再解释 `for (int v : tree[u])`

这是 C++ 的范围 for 循环（range-based for loop），
读法是：

“对于 tree[u] 里的每一个元素，依次取出放进变量 v 里”。

等价的老式写法是：

for (int i = 0; i < tree[u].size(); ++i) {
    int v = tree[u][i];
    dfs(v);
}

所以这句：

1	for (int v : tree[u])

其实就是：

“拿出当前节点u的每一个孩子v”。

四、然后执行 `dfs(v)`

dfs(v) 就是让程序“去访问这个孩子”。
因为DFS是递归，它自己又会：

打印v；
再去访问v的孩子；
直到走到底；
再回来继续访问下一个孩子。

整个过程像人钻洞：

你现在在洞口u；
看看有几个分岔口（孩子）；
每个口（v）都钻到底；
再返回来钻下一个。

五、加点“傻瓜式比喻”

假设 tree[1] = [2, 3]，tree[3] = [4, 5]。

程序运行：

dfs(1)

流程是：

进入1：
  打印1
  for循环拿到v=2 → dfs(2)
    打印2（没孩子）
  for循环拿到v=3 → dfs(3)
    打印3
    for循环拿到v=4 → dfs(4)
      打印4
    for循环拿到v=5 → dfs(5)
      打印5
全部结束

最后输出：1 2 3 4 5。

六、总结成一句话：

代码	含义
`for (int v : tree[u])`	从节点u的孩子列表中，一个一个取出孩子v
`dfs(v)`	对每个孩子再递归进行DFS
整体逻辑	“访问u → 对每个孩子都做DFS”

所以它其实干的事很像一句人话：

“我现在在u节点，我要去看它所有的孩子，每个孩子都得进去转一圈。”

如果你愿意，我可以帮你把这两行“展开成一整轮递归过程图”，
就能直观地看到程序是怎么一层层下去、又一层层回来的。

关于深搜老式写法的疑惑:

一、背景先记牢

我们在干的事是：

对当前节点 u，找到它的所有孩子，然后对每个孩子都 dfs(v)。

你可以理解成：

“我现在在 1 号点，看看它有几个孩子（比如 2 和 3），我一个个去拜访。”

二、先看大框架

for (int i = 0; i < tree[u].size(); ++i) {
    int v = tree[u][i];
    dfs(v);
}

这是一种普通的 for循环。
我们来翻译成中文：

“从 i = 0 开始，一直数到 tree[u].size() - 1，
每次都取出第 i 个孩子 v，
然后对这个孩子执行 dfs(v)。”

三、逐个词拆开解释

`tree[u]`

还是那句话：
tree[u] 是“u号节点的所有孩子”。
比如：

1	tree[1] = [2, 3]

说明 1 的孩子是 2 和 3。

`tree[u].size()`

表示孩子的数量。
比如 tree[1].size() = 2（因为1有两个孩子）。

所以：

1	for (int i = 0; i < tree[u].size(); ++i)

就等于：

“从第 0 个孩子开始，一直到最后一个孩子。”

`tree[u][i]`

这表示：

取出 u 的第 i 个孩子。

例如：

1	tree[1] = [2, 3]

那：

tree[1][0] = 2
tree[1][1] = 3

这两个值分别是“1号节点的第0个孩子”“1号节点的第1个孩子”。

`int v = tree[u][i];`

意思是：

把当前孩子的编号取出来，放进变量 v。

比如第一次循环：

i=0 → v=2
第二次循环：
i=1 → v=3

`dfs(v);`

这句就是：

“对孩子节点 v 再进行一次深度优先搜索。”

四、把整个循环翻译成人话：

以 u = 1 为例（假设 tree[1] = [2, 3]）：

for (int i = 0; i < 2; ++i) {
    int v = tree[1][i];
    dfs(v);
}

程序执行过程：

i	tree[1][i]	v的值	做的事
0	2	v=2	调用 `dfs(2)`
1	3	v=3	调用 `dfs(3)`

所以它干的事其实就是：

1 2	dfs(2); dfs(3);

只是写成循环自动处理，不用你手动列。

五、再画个逻辑图（想象程序脑子里的流程）

进入 dfs(1)
|
|—— i=0 → v=2 → dfs(2)
|—— i=1 → v=3 → dfs(3)

六、和新写法对比一下（你会立刻懂）

新写法（简化版）	老写法（展开版）
`for (int v : tree[u]) dfs(v);`	`for (int i = 0; i < tree[u].size(); ++i) { int v = tree[u][i]; dfs(v); }`

意思完全一样。
新写法更短、更清爽，
老写法是手动数下标的版本，适合旧标准（C++98）。

七、终极一句话总结

这三行代码的意思是：
“从第0个孩子开始，一个个取出来，
让每个孩子都跑一遍DFS。”

可是要是有一个点上没有孩子那为什么不会返回0呢

一、先看你说的情况

假设我们有一棵树：

1
2
3

  1
 / \
2   3

那在代码里是这样：

1
2
3

tree[1] = [2, 3];
tree[2] = [];
tree[3] = [];

也就是说：

1号节点有两个孩子；
2号和3号是“叶子节点”，没有孩子；
对应的 tree[2] 和 tree[3] 都是空的 vector<int>。

二、DFS会怎么跑？

void dfs(int u) {
    cout << u << " ";              // 先打印自己
    for (int v : tree[u]) {        // 遍历孩子
        dfs(v);                    // 深入孩子
    }
}

假设我们从 dfs(2) 开始执行。

第一步：进入函数

u = 2
打印出 2

第二步：执行 for 循环

1
2
3

for (int v : tree[2]) {
    dfs(v);
}

问题来了：tree[2] 是空的 []，对吧？

那for循环里根本就没有元素可以遍历。
程序就直接跳过循环体。

这时候程序不会“返回0”，因为循环本身没结果可返回。
C++ 的 for 不是返回值，而是一个控制语句，只控制“要不要执行循环体”。

三、重点理解：

C++ 的 for 不是函数，不会“返回”任何值。
所以你写：

1
2
3

for (int v : tree[u]) {
    dfs(v);
}

意思是：

“对每个孩子v，执行dfs(v)；
如果没孩子，那就什么都不做。”

它不会返回 0，也不会出错。
程序执行完循环后，就继续往下走（也就是递归结束）。

四、那DFS怎么“知道”到头了？

它其实通过两层逻辑：

如果 tree[u] 是空的，就不会进入for循环。
递归到这个节点时，发现没孩子可递归，于是自然返回上层。

举个流程（以 dfs(1) 为例）：

dfs(1)
 ├── 打印 1
 ├── 进入 for 循环 → 拿到 v=2 → dfs(2)
 │      ├── 打印 2
 │      ├── tree[2] 空 → 不进循环 → 返回
 │
 ├── 再拿 v=3 → dfs(3)
 │      ├── 打印 3
 │      ├── tree[3] 空 → 不进循环 → 返回
返回上层，结束

五、你要牢牢记住一句话：

没有孩子 ≠ 返回0。
只是没有孩子可以递归了，所以“自然结束函数”。

C++ 的函数如果写成 void dfs(...)，本身就没有返回值。
所以DFS这种函数从头到尾都不“return 某个数”，
它只是“执行完任务就返回上一级”。

六、打个比喻：

DFS像是你带孩子探险。

每次进一个洞（节点u），
你会说“我来了（打印u）”。
然后你看看有没有岔路（tree[u]）。
- 有，就挨个进去；
- 没有，就转身原路返回。

“返回”这个动作是自动发生的，不是“返回0”。

✅ 总结

情况	程序行为	原因
节点有孩子	依次对每个孩子递归DFS	for循环遍历非空vector
节点没孩子	for循环直接跳过，函数结束	空vector导致循环体不执行
是否返回0	否	dfs是`void`函数，无返回值

[例]P1030 [NOIP 2001 普及组] 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 $ \le 8$）。

输入格式

共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串，表示一棵二叉树的先序。

输入输出样例 #1

输入 #1

1
2

BADC
BDCA

输出 #1

ABCD

说明/提示

【题目来源】

NOIP 2001 普及组第三题

🚀 1. 你到底在做什么？

题目给你：

中序遍历（in-order）：左根右
后序遍历（post-order）：左右根

你要求出：

先序遍历（pre-order）：根左右

🚀 2. 为什么能通过「中序 + 后序」推回一棵唯一的二叉树？

关键就在：

后序的最后一个字符一定是根节点
中序中，根节点的位置把树分成左子树和右子树

就这么简单。

比如：

中序：B A D C
后序：B D C A

后序最后是 A，所以 A 是根。

然后看看 A 在中序中出现在哪：
B A D C
↑
A 在下标 1

左边 B → 左子树
右边 D C → 右子树

这样就切出来了。

🚀 3. 那为什么一定要用 map？

因为我要知道：

字母 A 在中序字符串里是第几位？

你可以用 for 循环扫：

1 2	for (int i = 0; i < in.size(); i++) if (in[i] == root) k = i;

但更聪明的是：

我先建一个查表（map）：

pos['B'] = 0;
pos['A'] = 1;
pos['D'] = 2;
pos['C'] = 3;

这样我要找位置用：

1	int k = pos[root];

一查就知道，非常快、非常干净。

🚀 4. 为什么用递归 build？

因为二叉树天然就是递归结构：

当前根节点确定了
左子树也按照相同逻辑构建
右子树也一样

递归适合干“重复但规模缩小”的事。

🚀 5. 核心代码（逐行傻瓜讲解）

我把代码拆开讲，你秒懂：

读取输入

1	cin >> in >> post;

读两个字符串，中序和后序。

建立 map：每个字符在中序中的位置

1 2	for (int i = 0; i < in.size(); i++) pos[in[i]] = i;

以后我要查 A 在哪里，只要：

pos['A']

build 函数：递归构建先序字符串

1	void build(int inL, int inR, int postL, int postR) {

表示我们现在要处理的中序区间 和 后序区间是什么。

终止条件

1	if (inL > inR) return;

左边超过右边，一棵空树，啥都别干。

后序最后一个一定是根

1	char root = post[postR];

比如后序是 BDCA，最后的 A 是根。

先序输出顺序：根在最前

1	pre.push_back(root);

先序是：根左右
所以先把根输出出去。

找根在中序的位置

1	int k = pos[root];

pos 是我们提前做好查表，用 map 查一次就出来。

计算左子树的大小

1	int leftSize = k - inL;

比如中序：

1	inL ... 左子树 ... k(root) ... 右子树 ... inR

很自然 leftSize = 左子树长度。

递归构建左子树

1	build(inL, k - 1, postL, postL + leftSize - 1);

中序：左边部分
后序：左边部分

递归构建右子树

1	build(k + 1, inR, postL + leftSize, postR - 1);

右子树的中序和后序区间自己算出来的。

🚀 6. 完整源码（含解释版）

下面是你需要的完整代码：

#include <iostream>
#include <map>
using namespace std;

string in, post;    // 输入：中序和后序
string pre;         // 输出：先序
map<char, int> pos; // 记录每个节点在中序中的位置

// 构建先序遍历
void build(int inL, int inR, int postL, int postR) {
    // 空区间，返回
    if (inL > inR) return;

    // 后序最后一个是根
    char root = post[postR];
    pre.push_back(root); // 先序先输出根

    // 根在中序中的下标
    int k = pos[root];

    // 左子树大小 = 中序左半长度
    int leftSize = k - inL;

    // 构建左子树
    build(inL, k - 1, postL, postL + leftSize - 1);

    // 构建右子树
    build(k + 1, inR, postL + leftSize, postR - 1);
}

int main() {
    cin >> in >> post;

    // 建表：O(n) 记录每个字符在中序里的位置
    for (int i = 0; i < in.size(); i++)
        pos[in[i]] = i;

    build(0, in.size() - 1, 0, post.size() - 1);

    cout << pre << endl;
    return 0;
}

举例论证

✅ 例子 1：题目同类型（简单对称）

中序：BADC
后序：BDCA

步骤 1：后序最后一个是根

根 = A

中序定位 A：
B A D C
↑
位置 index = 1

左子树中序：B
右子树中序：D C

后序拆分：

左子树后序：B
右子树后序：D C

步骤 2：递归左子树

中序：B
后序：B

后序最后一个 → 根 = B
没有左右子树。

步骤 3：递归右子树

中序：D C
后序：D C

根 = C

中序定位 C：
D C
↑
index = 1

左：D
右：空

左子树后序：D
右子树后序：空

步骤 4：构建右子树的左子树

中序：D
后序：D

根 = D，无左右子树。

🌟 最终先序输出顺序：

A B C D

完全正确。

✅ **例子 2:

例如一棵向左的链：

    D
   /
  C
 /
B
/
A

中序（左根右）：ABCD
后序（左右根）：ABCD

模拟构建

后序最后 → 根 = D
中序中 ABC | D
左子树：中序 ABC，后序 ABC
再取根 = C
左子树：AB
根 = B
左子树：A
根 = A

先序（根左右）：

D C B A

验证：完全正确。

✅ 例子 3：所有节点都在右边（链式右树）

结构：

A
 \
  B
   \
    C
     \
      D

中序：ABCD
后序：BCDA

模拟构建

根 = D
中序：ABC | D → 右子树是 ABC
对右子树：
- 后序：B C A
- 根 = A
中序：B C | A
对右子树：
- 后序：B C
- 根 = C
中序：B | C
左子树：B

先序：

D A C B

完全正确。

✅ 例子 4：典型杂乱结构

树如下：

  F
 / \
B   G
 \   \
  D   I

手算遍历结果

中序（左根右）：

左子树(B D) → B D
根 F
右子树(G I) → G I

中序 = B D F G I

后序（左右根）：

左子树(B D) → D B
右子树(G I) → I G
根 F

后序 = D B I G F

模拟重建

给你中序：BDFGI
后序：DBIGF

第一次：

根 = F
中序分为：BD | F | GI

左子树：

中序：BD
后序：DB
根 = B
中序 | B | D → 右子树是 D

右子树：

中序：GI
后序：IG
根 = G
右子树 = I

先序输出：

F B D G I

符合真实结构。

🔥 你现在要记住的唯一原则：

后序最后一个字符一定是根；在中序中找到根的位置，就能把左右子树精确切开。

深搜的相关的知识&树的一些

深搜的相关的知识

二、我们要干的事

三、先造存储结构（这部分最关键）

定义：

四、把上面的树存进去

五、写 DFS 函数（核心！）

六、主函数完整代码

七、要理解的关键点

关于深搜的核心写法的疑惑:

一、先看原句

二、先解释 tree[u]

三、再解释 for (int v : tree[u])

四、然后执行 dfs(v)

五、加点“傻瓜式比喻”

六、总结成一句话：

关于深搜老式写法的疑惑:

一、背景先记牢

二、先看大框架

三、逐个词拆开解释

tree[u]

tree[u].size()

tree[u][i]

int v = tree[u][i];

dfs(v);

四、把整个循环翻译成人话：

五、再画个逻辑图（想象程序脑子里的流程）

六、和新写法对比一下（你会立刻懂）

七、终极一句话总结

可是要是有一个点上没有孩子 那为什么不会返回0呢

一、先看你说的情况

二、DFS会怎么跑？

第一步：进入函数

第二步：执行 for 循环

三、重点理解：

四、那DFS怎么“知道”到头了？

五、你要牢牢记住一句话：

六、打个比喻：

✅ 总结

[例]P1030 [NOIP 2001 普及组] 求先序排列

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

🚀 1. 你到底在做什么？

🚀 2. 为什么能通过「中序 + 后序」推回一棵唯一的二叉树？

比如：

🚀 3. 那为什么一定要用 map？

🚀 4. 为什么用递归 build？

🚀 5. 核心代码（逐行傻瓜讲解）

读取输入

建立 map：每个字符在中序中的位置

build 函数：递归构建先序字符串

终止条件

后序最后一个一定是根

先序输出顺序：根在最前

找根在中序的位置

计算左子树的大小

递归构建左子树

递归构建右子树

🚀 6. 完整源码（含解释版）

举例论证

✅ 例子 1：题目同类型（简单对称）

步骤 1：后序最后一个是根

步骤 2：递归左子树

步骤 3：递归右子树

步骤 4：构建右子树的左子树

🌟 最终先序输出顺序：

✅ **例子 2:

模拟构建

✅ 例子 3：所有节点都在右边（链式右树）

模拟构建

✅ 例子 4：典型杂乱结构

手算遍历结果

模拟重建

第一次：

左子树：

二、先解释 `tree[u]`

三、再解释 `for (int v : tree[u])`

四、然后执行 `dfs(v)`

`tree[u]`

`tree[u].size()`

`tree[u][i]`

`int v = tree[u][i];`

`dfs(v);`

可是要是有一个点上没有孩子那为什么不会返回0呢