二叉树专题练习 ——基于罗勇军老师的《蓝桥杯算法入门C/C++》

一、B3642 二叉树的遍历 - 洛谷

算法代码：

1. 代码结构

头文件和命名空间：

常量定义：

结构体定义：

前序遍历函数：

中序遍历函数：

后序遍历函数：

主函数：

2. 代码思路

输入处理：

树的构建：

遍历输出：

3. 代码优化建议

输入验证：

内存管理：

代码复用：

4. 示例输入输出

5. 总结

评测记录：

二、 1.子树的大小 - 蓝桥云课

算法代码：

问题：

代码思路

1. 输入部分

2. 初始化变量

3. 模拟子树扩展过程

4. 输出结果

5. 结束

代码功能分析

举例说明

运行过程

初始化：

第一次循环：

第二次循环：

第三次循环：

输出结果：

总结

三、 1.FBI树 - 蓝桥云课

算法代码：

代码思路

1. 全局变量

2. 辅助函数

3. 构建 FBI树

4. 后序遍历

5. 主函数

代码功能分析

输入处理：

FBI树构建：

后序遍历输出：

示例说明

运行过程

输入：

构建 FBI树：

后序遍历：

输出

总结

四、1.完全二叉树的权值 - 蓝桥云课

算法代码：

代码思路分析

递归函数 dfs:

主函数 main:

代码优化建议

避免重复计算:

尾递归优化:

代码可读性:

优化后的代码示例

优化点解释

前缀和数组:

代码可读性:

五、 P1827 [USACO3.4] 美国血统 American Heritage - 洛谷

算法代码：

代码思路分析

输入处理：

递归函数 work：

主函数 main：

代码优化建议

避免不必要的字符串拷贝：

使用引用传递参数：

增加输入验证：

优化后的代码示例

优化点解释

评测记录：

六、 P1030 [NOIP 2001 普及组] 求先序排列 - 洛谷

算法代码：

代码思路分析

输入处理：

递归函数 beford：

主函数 main：

代码优化建议

避免不必要的字符串拷贝：

使用引用传递参数：

增加输入验证：

优化后的代码示例

优化点解释

索引范围传递：

引用传递：

递归终止条件：

输出根节点：

评测记录：

一、B3642 二叉树的遍历 - 洛谷

算法代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct Node
{int v;int ls,rs;
}t[N];void preorder(int p)
{if(p!=0){cout<<t[p].v<<" ";preorder(t[p].ls);preorder(t[p].rs);}
}void midorder(int p)
{if(p!=0){midorder(t[p].ls);cout<<t[p].v<<" ";midorder(t[p].rs);}
}void postorder(int p)
{if(p!=0){postorder(t[p].ls);postorder(t[p].rs);cout<<t[p].v<<" ";}
}int main()
{int n;cin>>n;for(int i=1;i<=n;i++){int a,b;cin>>a>>b;t[i].v=i;t[i].ls=a;t[i].rs=b;}preorder(1);cout<<endl;midorder(1);cout<<endl;postorder(1);cout<<endl;return 0;
}

这段代码实现了一个简单的二叉树结构，并提供了前序遍历、中序遍历和后序遍历的功能。以下是对代码的详细解释和思路分析：

1. 代码结构

头文件和命名空间：
```
#include<bits/stdc++.h>
using namespace std;
```
这里使用了万能头文件 <bits/stdc++.h>，它包含了C++标准库中的大部分头文件。using namespace std; 是为了避免每次调用标准库函数时都要写 std::。
常量定义：
```
const int N=100005;
```
定义了一个常量 N，表示树的最大节点数。
结构体定义：
```
struct Node
{int v;int ls,rs;
}t[N];
```
定义了一个 Node 结构体，表示二叉树的节点。每个节点包含三个成员：
- v：节点的值。
- ls：左子节点的索引。
- rs：右子节点的索引。
数组 t[N] 用于存储所有节点。
前序遍历函数：
```
void preorder(int p)
{if(p!=0){cout<<t[p].v<<" ";preorder(t[p].ls);preorder(t[p].rs);}
}
```
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。递归实现。
中序遍历函数：
```
void midorder(int p)
{if(p!=0){midorder(t[p].ls);cout<<t[p].v<<" ";midorder(t[p].rs);}
}
```
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。递归实现。
后序遍历函数：
```
void postorder(int p)
{if(p!=0){postorder(t[p].ls);postorder(t[p].rs);cout<<t[p].v<<" ";}
}
```
后序遍历的顺序是：左子树 -> 右子树 -> 根节点。递归实现。
主函数：
```
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){int a,b;cin>>a>>b;t[i].v=i;t[i].ls=a;t[i].rs=b;}preorder(1);cout<<endl;midorder(1);cout<<endl;postorder(1);cout<<endl;return 0;
}
```
- 首先输入节点数 n。
- 然后依次输入每个节点的左子节点和右子节点的索引，并初始化节点的值。
- 最后分别调用前序、中序、后序遍历函数，输出遍历结果。

2. 代码思路

输入处理：
- 首先读取节点数 n。
- 然后依次读取每个节点的左子节点和右子节点的索引，并初始化节点的值。
树的构建：
- 通过输入的左右子节点索引，构建二叉树结构。
遍历输出：
- 分别调用前序、中序、后序遍历函数，输出遍历结果。

3. 代码优化建议

输入验证：
- 可以在输入时增加对节点索引的验证，确保输入的索引在有效范围内（1到n）。
内存管理：
- 如果节点数 n 很大，可以考虑动态分配内存，而不是使用固定大小的数组。
代码复用：
- 可以将遍历函数的公共部分提取出来，减少代码重复。

4. 示例输入输出

假设输入如下：

表示有5个节点，树的结构如下：

输出应为：

1 2 4 5 3 
4 2 5 1 3 
4 5 2 3 1

5. 总结

这段代码实现了一个简单的二叉树结构，并提供了前序、中序、后序遍历的功能。代码结构清晰，逻辑简单，适合初学者理解和学习二叉树的遍历算法。

评测记录：

二、 1.子树的大小 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{int t;cin>>t;while(t--){ll n,m,k;cin>>n>>m>>k;ll ans=1;ll ls=k,rs=k;while(1){ls=(ls-1)*m+2;rs=rs*m+1;if(ls>n){break;}if(rs>=n){ans+=n-ls+1;break;}ans+=rs-ls+1;}cout<<ans<<endl;}return 0;
}

问题：

第u个节点的最左孩子的编号是多少?

第u号节点前面有u-1个点,每个节点各有个孩子,再加上1号节点,可得第u个节点的左孩子下标为(u-1)*m+2。
例如该图中的3号节点,求它的最左孩子的编号。
3号节点前面有两个点,即1号节点和2号节点,每个节点都有3个孩子,1号节点的孩子是2、3、4,2号节点的孩子是5、6、7,共6个孩子。那么?号节点的最左孩子的编号是1十2x3+1-8。

同理,第u个节点的孩子如果是满的,它的最右孩子的编号为u*m+1。

分析第u个节点的情况:

节点u在最后一层。此时节点u的最左孩子的编号大于n,即(u-1)*m+2>n,说明这个孩子不存在,也就是说节点u在最后一层,那么以节点u为根的子树的节点数量是1,就是u自己。
节点u不是最后一层,且u的孩子是满的,即最右孩子的编号u*m+1<n。此时可以继续分析u的孩子的情况。
节点u不是最后一层,u有左孩子,但是孩子不满,此时u在倒数第2层,它的最右孩子的编号就是n。以u为根的子树的数量=右孩子编号-(左孩子编号一1)+u自己,即n-((u-1)*m+1)+1=n-u*m十m。

这段代码的目的是计算在完全 mm 叉树中，第 kk 个结点对应的子树所包含的结点数量。以下是代码的详细思路和解释：

代码思路

1. 输入部分

int t;
cin >> t;
while (t--) {ll n, m, k;cin >> n >> m >> k;

首先读取测试用例的数量 tt。
对于每个测试用例，读取三个整数 n、m 和 k，分别表示树的结点总数、树的叉数和目标结点的编号。

2. 初始化变量

ll ans = 1;
ll ls = k, rs = k;

ans 用于记录最终的结果，初始值为 1（表示当前结点本身）。
ls 和 rs 分别表示当前子树的左边界和右边界，初始值为 k。

3. 模拟子树扩展过程

while (1) {ls = (ls - 1) * m + 2;rs = rs * m + 1;if (ls > n) {break;}if (rs >= n) {ans += n - ls + 1;break;}ans += rs - ls + 1;
}

这是一个无限循环，通过 break 语句退出。
每次循环中：
- 更新左边界 ls 和右边界 rs：
  - ls = (ls - 1) * m + 2：根据完全 m 叉树的性质，计算下一层的最左结点。
  - rs = rs * m + 1：根据完全 m 叉树的性质，计算下一层的最右结点。
- 检查边界条件：
  - 如果 ls > n，说明当前子树已经超出树的结点总数，直接退出循环。
  - 如果 rs >= n，说明当前子树部分超出树的结点总数，将有效部分（n - ls + 1）加到 ans 中，然后退出循环。
  - 否则，将当前层的结点数量（rs - ls + 1）加到 ans 中。

4. 输出结果

cout << ans << endl;

输出当前测试用例的结果。

5. 结束

return 0;

程序结束。

代码功能分析

这段代码的核心功能是计算完全 m 叉树中第 k个结点对应的子树所包含的结点数量。具体来说：

初始子树：只包含第 k个结点，长度为 1。
扩展规则：
- 左边界 ls 更新为 (ls - 1) * m + 2，表示下一层的最左结点。
- 右边界 rs 更新为 rs * m + 1，表示下一层的最右结点。
终止条件：
- 如果左边界 ls 超过 n，停止扩展。
- 如果右边界 rs 超过 n，只计算有效部分。

举例说明

假设输入如下：

1
10 2 1

运行过程

初始化：
- n = 10，m = 2，k = 1。
- ans = 1，ls = 1，rs = 1。
第一次循环：
- 更新 ls = (1 - 1) * 2 + 2 = 2。
- 更新 rs = 1 * 2 + 1 = 3。
- 检查边界：
  - ls = 2 <= 10，rs = 3 <= 10。
  - 将区间 [2, 3] 的长度 2 加到 ans 中，ans = 3。
第二次循环：
- 更新 ls = (2 - 1) * 2 + 2 = 4。
- 更新 rs = 3 * 2 + 1 = 7。
- 检查边界：
  - ls = 4 <= 10，rs = 7 <= 10。
  - 将区间 [4, 7] 的长度 4 加到 ans 中，ans = 7。
第三次循环：
- 更新 ls = (4 - 1) * 2 + 2 = 8。
- 更新 rs = 7 * 2 + 1 = 15。
- 检查边界：
  - ls = 8 <= 10，rs = 15 > 10。
  - 只计算有效部分 [8, 10] 的长度 3，加到 ans 中，ans = 10。
  - 退出循环。
输出结果：
- ans = 10。

总结

这段代码通过模拟完全 m叉树的子树扩展过程，计算第 k 个结点对应的子树所包含的结点数量。代码的逻辑清晰，能够高效地处理大规模的输入数据。

三、 1.FBI树 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;char s[1100],tree[4400];int ls(int p)
{return p<<1;
}int rs(int p)
{return p<<1|1;
}void build_FBI(int p,int left,int right)
{if(left==right){if(s[right]=='1'){tree[p]='I';}else{tree[p]='B';}return;}int mid=(left+right)/2;build_FBI(ls(p),left,mid);build_FBI(rs(p),mid+1,right);if(tree[ls(p)]=='B'&&tree[rs(p)]=='B'){tree[p]='B';}else if(tree[ls(p)]=='I'&&tree[rs(p)]=='I'){tree[p]='I';}else{tree[p]='F';}
}void postorder(int p)
{if(tree[ls(p)]){postorder(ls(p));}if(tree[rs(p)]){postorder(rs(p));}printf("%c",tree[p]);
}int main()
{int n;cin>>n;cin>>s+1;build_FBI(1,1,strlen(s+1));postorder(1);
}

这段代码实现了 FBI树 的构建和后序遍历输出。以下是代码的详细思路和解释：

代码思路

1. 全局变量

char s[1100], tree[4400];

s：存储输入的“01”串。
tree：用于存储 FBI树的结点类型（F、B 或 I）。

2. 辅助函数

int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }

ls(p)：返回结点 p 的左子结点的索引（2 * p）。
rs(p)：返回结点 p 的右子结点的索引（2 * p + 1）。

3. 构建 FBI树

void build_FBI(int p, int left, int right) {if (left == right) {if (s[right] == '1') {tree[p] = 'I';} else {tree[p] = 'B';}return;}int mid = (left + right) / 2;build_FBI(ls(p), left, mid);build_FBI(rs(p), mid + 1, right);if (tree[ls(p)] == 'B' && tree[rs(p)] == 'B') {tree[p] = 'B';} else if (tree[ls(p)] == 'I' && tree[rs(p)] == 'I') {tree[p] = 'I';} else {tree[p] = 'F';}
}

功能：递归地构建 FBI树。
参数：
- p：当前结点的索引。
- left 和 right：当前结点对应的字符串区间。
逻辑：
- 如果 left == right，说明当前结点是叶子结点，根据字符 s[right] 设置结点类型（B 或 I）。
- 否则，将字符串分成两半，递归构建左子树和右子树。
- 根据左右子树的类型，确定当前结点的类型：
  - 如果左右子树都是 B，当前结点为 B。
  - 如果左右子树都是 I，当前结点为 I。
  - 否则，当前结点为 F。

4. 后序遍历

void postorder(int p) {if (tree[ls(p)]) {postorder(ls(p));}if (tree[rs(p)]) {postorder(rs(p));}printf("%c", tree[p]);
}

功能：递归地输出 FBI树的后序遍历结果。
参数：
- p：当前结点的索引。
逻辑：
- 如果左子树存在，递归遍历左子树。
- 如果右子树存在，递归遍历右子树。
- 输出当前结点的类型。

5. 主函数

int main() {int n;cin >> n;cin >> s + 1;build_FBI(1, 1, strlen(s + 1));postorder(1);
}

功能：读取输入，构建 FBI树，并输出后序遍历结果。
逻辑：
- 读取整数 n 和字符串 s。
- 调用 build_FBI 函数构建 FBI树。
- 调用 postorder 函数输出后序遍历结果。

代码功能分析

输入处理：
- 读取字符串 s 和整数 n。
- 字符串 s 从索引 1 开始存储，方便后续处理。
FBI树构建：
- 使用递归方法构建 FBI树。
- 每个结点的类型由其对应的字符串区间决定。
后序遍历输出：
- 通过递归方法输出 FBI树的后序遍历结果。

示例说明

假设输入如下：

3
00111011

运行过程

输入：
- n = 3，字符串 s = 00111011。
构建 FBI树：
- 根结点对应整个字符串 00111011，类型为 F。
- 左子树对应 0011，类型为 F。
- 右子树对应 1011，类型为 F。
- 继续递归分割，直到叶子结点。
后序遍历：
- 遍历顺序：左子树 -> 右子树 -> 根结点。
- 输出结果：BBFIIFIIFIIFF。

输出

BBFIIFIIFIIFF

总结

这段代码通过递归方法构建 FBI树，并输出后序遍历结果。
代码逻辑清晰，能够高效地处理输入数据。
时间复杂度为 O(2N)O(2N)，因为需要遍历所有结点。

四、1.完全二叉树的权值 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;// 递归函数，计算从某一层开始的权值之和
pair<int, int> dfs(int depth, int start, int N, const vector<int>& A) {if (start >= N) {return {0, depth - 1}; // 如果超出范围，返回 0 和上一层的深度}// 计算当前层的结束索引int end = min(start + (1 << (depth - 1)), N);int sum = 0;for (int i = start; i < end; ++i) {sum += A[i];}// 递归计算下一层的权值之和auto next = dfs(depth + 1, end, N, A);// 比较当前层和下一层的权值之和if (sum >= next.first) {return {sum, depth}; // 如果当前层更大，返回当前层的深度} else {return next; // 否则返回下一层的结果}
}int main() {int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; ++i) {cin >> A[i];}// 调用递归函数，从深度 1 开始auto result = dfs(1, 0, N, A);// 输出结果cout << result.second << endl;return 0;
}

这段代码的主要功能是计算一个数组中某一层的权值之和，并返回权值之和最大的层数。代码的核心思想是通过递归遍历数组的每一层，计算每一层的权值之和，并比较当前层和下一层的权值之和，最终返回权值之和最大的层数。

代码思路分析

递归函数 dfs:
- 参数:
  - depth: 当前层的深度。
  - start: 当前层的起始索引。
  - N: 数组的总长度。
  - A: 输入的数组。
- 返回值:
  - 返回一个 pair<int, int>，其中第一个元素是当前层的权值之和，第二个元素是权值之和最大的层数。
- 递归终止条件:
  - 如果 start >= N，说明已经超出数组范围，返回 {0, depth - 1}，表示上一层的深度。
- 计算当前层的权值之和:
  - 计算当前层的结束索引 end，并遍历从 start 到 end 的元素，累加得到当前层的权值之和 sum。
- 递归调用:
  - 递归调用 dfs，计算下一层的权值之和。
- 比较当前层和下一层的权值之和:
  - 如果当前层的权值之和 sum 大于等于下一层的权值之和，返回当前层的深度 depth。
  - 否则，返回下一层的结果。
主函数 main:
- 读取输入的数组长度 N 和数组 A。
- 调用 dfs 函数，从深度 1 开始递归计算。
- 输出结果，即权值之和最大的层数。

代码优化建议

避免重复计算:
- 当前代码在每一层都重新计算了当前层的权值之和，可以考虑使用前缀和数组来优化，避免重复计算。
尾递归优化:
- 递归调用可能会导致栈溢出，可以考虑使用尾递归优化或迭代的方式来实现。
代码可读性:
- 可以增加一些注释，解释每一部分的逻辑，提高代码的可读性。

优化后的代码示例

#include <bits/stdc++.h>
using namespace std;// 递归函数，计算从某一层开始的权值之和
pair<int, int> dfs(int depth, int start, int N, const vector<int>& A, const vector<int>& prefixSum) {if (start >= N) {return {0, depth - 1}; // 如果超出范围，返回 0 和上一层的深度}// 计算当前层的结束索引int end = min(start + (1 << (depth - 1)), N);int sum = prefixSum[end] - prefixSum[start]; // 使用前缀和计算当前层的权值之和// 递归计算下一层的权值之和auto next = dfs(depth + 1, end, N, A, prefixSum);// 比较当前层和下一层的权值之和if (sum >= next.first) {return {sum, depth}; // 如果当前层更大，返回当前层的深度} else {return next; // 否则返回下一层的结果}
}int main() {int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; ++i) {cin >> A[i];}// 计算前缀和数组vector<int> prefixSum(N + 1, 0);for (int i = 0; i < N; ++i) {prefixSum[i + 1] = prefixSum[i] + A[i];}// 调用递归函数，从深度 1 开始auto result = dfs(1, 0, N, A, prefixSum);// 输出结果cout << result.second << endl;return 0;
}

优化点解释

前缀和数组:
- 使用前缀和数组 prefixSum 来快速计算任意区间的和，避免了重复计算。
代码可读性:
- 增加了注释，解释了每一部分的逻辑，提高了代码的可读性。

通过以上优化，代码的效率得到了提升，同时也更容易理解和维护。

五、 P1827 [USACO3.4] 美国血统 American Heritage - 洛谷

算法代码：

#include<string>
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
string pre,inor;
void work(string pre,string inor)
{if(pre.empty())return;//如果序列空了，就没必要继续了char root=pre[0];//取到前序序列的首字母，即根节点int k=inor.find(root);//找到中序序列中根节点的位置pre.erase(pre.begin());//删去前序序列中的根节点string leftpre=pre.substr(0,k);//从0开始切割k个string rightpre=pre.substr(k);//从k开始切割到最后string leftinor=inor.substr(0,k);//从0开始切割k个string rightinor=inor.substr(k+1);//从k+1开始切割到最后work(leftpre,leftinor);work(rightpre,rightinor);printf("%c",root);//因为要输出后序序列，所以是左右根//先遍历左子树，再右子树，再根节点
}
int main()
{cin>>inor>>pre;work(pre,inor);putchar('\n');return 0;
}

这段代码的目的是根据给定的前序遍历（pre）和中序遍历（inor）结果，输出二叉树的后序遍历结果。代码的核心思想是通过递归的方式重建二叉树，并在递归过程中输出后序遍历的结果。

代码思路分析

输入处理：
- 从标准输入读取中序遍历（inor）和前序遍历（pre）的字符串。
递归函数 work：
- 参数：
  - pre：当前子树的前序遍历结果。
  - inor：当前子树的中序遍历结果。
- 终止条件：
  - 如果 pre 为空，说明当前子树已经处理完毕，直接返回。
- 根节点：
  - 前序遍历的第一个字符是当前子树的根节点（root）。
- 中序遍历中根节点的位置：
  - 使用 inor.find(root) 找到根节点在中序遍历中的位置 k。
- 分割前序和中序遍历：
  - 将前序遍历和中序遍历分割为左子树和右子树的部分。
  - 左子树的前序遍历：pre.substr(0, k)。
  - 右子树的前序遍历：pre.substr(k)。
  - 左子树的中序遍历：inor.substr(0, k)。
  - 右子树的中序遍历：inor.substr(k + 1)。
- 递归处理左右子树：
  - 递归调用 work 处理左子树和右子树。
- 输出根节点：
  - 在递归处理完左右子树后，输出根节点，以实现后序遍历（左-右-根）的顺序。
主函数 main：
- 读取输入的中序遍历和前序遍历字符串。
- 调用 work 函数开始递归处理。
- 输出换行符，结束程序。

代码优化建议

避免不必要的字符串拷贝：
- 当前代码在每次递归调用时都会创建新的子字符串，这可能会导致性能问题，尤其是在处理大规模数据时。可以通过传递索引范围来避免字符串拷贝。
使用引用传递参数：
- 将 pre 和 inor 作为引用传递，避免不必要的拷贝。
增加输入验证：
- 确保输入的前序遍历和中序遍历是有效的，例如长度一致且包含相同的字符。

优化后的代码示例

#include <iostream>
#include <string>
using namespace std;// 递归函数，根据前序遍历和中序遍历的结果输出后序遍历
void work(const string& pre, int preStart, int preEnd, const string& inor, int inStart, int inEnd) {// 如果前序遍历或中序遍历的范围无效，直接返回if (preStart > preEnd || inStart > inEnd) {return;}// 前序遍历的第一个字符是当前子树的根节点char root = pre[preStart];// 在中序遍历中找到根节点的位置int k = inor.find(root, inStart);// 计算左子树的大小int leftSize = k - inStart;// 递归处理左子树// 左子树的前序遍历范围：preStart + 1 到 preStart + leftSize// 左子树的中序遍历范围：inStart 到 k - 1work(pre, preStart + 1, preStart + leftSize, inor, inStart, k - 1);// 递归处理右子树// 右子树的前序遍历范围：preStart + leftSize + 1 到 preEnd// 右子树的中序遍历范围：k + 1 到 inEndwork(pre, preStart + leftSize + 1, preEnd, inor, k + 1, inEnd);// 输出根节点，实现后序遍历的顺序（左-右-根）cout << root;
}int main() {string inor, pre;// 读取中序遍历和前序遍历的字符串cin >> inor >> pre;// 调用递归函数，初始范围为整个字符串的范围work(pre, 0, pre.size() - 1, inor, 0, inor.size() - 1);// 输出换行符cout << endl;return 0;
}

优化点解释

索引范围传递：
- 使用 preStart, preEnd, inStart, inEnd 来表示当前处理的范围，避免创建新的子字符串。
引用传递：
- 将 pre 和 inor 作为 const string& 传递，避免不必要的拷贝。
递归终止条件：
- 当 preStart > preEnd 或 inStart > inEnd 时，表示当前子树为空，直接返回。
输出根节点：
- 在递归处理完左右子树后，输出根节点，以实现后序遍历的顺序。

通过以上优化，代码的效率得到了提升，同时也更容易理解和维护。

评测记录：

六、 P1030 [NOIP 2001 普及组] 求先序排列 - 洛谷

算法代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void beford(string in,string after){if (in.size()>0){char ch=after[after.size()-1];cout<<ch;//找根输出int k=in.find(ch);beford(in.substr(0,k),after.substr(0,k));beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树；}
}
int main(){string inord,aftord;cin>>inord;cin>>aftord;//读入beford(inord,aftord);cout<<endl;return 0;
}

这段代码的目的是根据给定的中序遍历（inord）和后序遍历（aftord）结果，输出二叉树的前序遍历结果。代码的核心思想是通过递归的方式重建二叉树，并在递归过程中输出前序遍历的结果。

代码思路分析

输入处理：
- 从标准输入读取中序遍历（inord）和后序遍历（aftord）的字符串。
递归函数 beford：
- 参数：
  - in：当前子树的中序遍历结果。
  - after：当前子树的后序遍历结果。
- 终止条件：
  - 如果 in 的大小为 0，说明当前子树已经处理完毕，直接返回。
- 根节点：
  - 后序遍历的最后一个字符是当前子树的根节点（ch）。
- 输出根节点：
  - 输出根节点，以实现前序遍历（根-左-右）的顺序。
- 中序遍历中根节点的位置：
  - 使用 in.find(ch) 找到根节点在中序遍历中的位置 k。
- 递归处理左右子树：
  - 左子树的中序遍历：in.substr(0, k)。
  - 左子树的后序遍历：after.substr(0, k)。
  - 右子树的中序遍历：in.substr(k + 1)。
  - 右子树的后序遍历：after.substr(k, in.size() - k - 1)。
- 递归调用：
  - 递归调用 beford 处理左子树和右子树。
主函数 main：
- 读取输入的中序遍历和后序遍历字符串。
- 调用 beford 函数开始递归处理。
- 输出换行符，结束程序。

代码优化建议

避免不必要的字符串拷贝：
- 当前代码在每次递归调用时都会创建新的子字符串，这可能会导致性能问题，尤其是在处理大规模数据时。可以通过传递索引范围来避免字符串拷贝。
使用引用传递参数：
- 将 in 和 after 作为引用传递，避免不必要的拷贝。
增加输入验证：
- 确保输入的中序遍历和后序遍历是有效的，例如长度一致且包含相同的字符。

优化后的代码示例

#include <iostream>
#include <string>
using namespace std;// 递归函数，根据中序遍历和后序遍历的结果输出前序遍历
void beford(const string& in, int inStart, int inEnd, const string& after, int afterStart, int afterEnd) {// 如果中序遍历或后序遍历的范围无效，直接返回if (inStart > inEnd || afterStart > afterEnd) {return;}// 后序遍历的最后一个字符是当前子树的根节点char ch = after[afterEnd];// 输出根节点，实现前序遍历的顺序（根-左-右）cout << ch;// 在中序遍历中找到根节点的位置int k = in.find(ch, inStart);// 计算左子树的大小int leftSize = k - inStart;// 递归处理左子树// 左子树的中序遍历范围：inStart 到 k - 1// 左子树的后序遍历范围：afterStart 到 afterStart + leftSize - 1beford(in, inStart, k - 1, after, afterStart, afterStart + leftSize - 1);// 递归处理右子树// 右子树的中序遍历范围：k + 1 到 inEnd// 右子树的后序遍历范围：afterStart + leftSize 到 afterEnd - 1beford(in, k + 1, inEnd, after, afterStart + leftSize, afterEnd - 1);
}int main() {string inord, aftord;// 读取中序遍历和后序遍历的字符串cin >> inord >> aftord;// 调用递归函数，初始范围为整个字符串的范围beford(inord, 0, inord.size() - 1, aftord, 0, aftord.size() - 1);// 输出换行符cout << endl;return 0;
}

优化点解释

索引范围传递：
- 使用 inStart, inEnd, afterStart, afterEnd 来表示当前处理的范围，避免创建新的子字符串。
引用传递：
- 将 in 和 after 作为 const string& 传递，避免不必要的拷贝。
递归终止条件：
- 当 inStart > inEnd 或 afterStart > afterEnd 时，表示当前子树为空，直接返回。
输出根节点：
- 在递归处理左右子树前，输出根节点，以实现前序遍历的顺序（根-左-右）。

通过以上优化，代码的效率得到了提升，同时也更容易理解和维护。