二叉树专题练习 ——基于罗勇军老师的《蓝桥杯算法入门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
2 3
4 5
0 0
0 0
0 0

表示有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个节点的情况:

1. 节点u在最后一层。此时节点u的最左孩子的编号大于n,即(u-1)*m+2>n,说明这个孩子不存在,也就是说节点u在最后一层,那么以节点u为根的子树的节点数量是1,就是u自己。
2. 节点u不是最后一层,且u的孩子是满的,即最右孩子的编号u*m+1<n。此时可以继续分析u的孩子的情况。
3. 节点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个结点对应的子树所包含的结点数量。具体来说：

1. 初始子树：只包含第 k个结点，长度为 1。

2. 扩展规则：

   • 左边界 ls 更新为 (ls - 1) * m + 2，表示下一层的最左结点。

   • 右边界 rs 更新为 rs * m + 1，表示下一层的最右结点。

3. 终止条件：

   • 如果左边界 ls 超过 n，停止扩展。

   • 如果右边界 rs 超过 n，只计算有效部分。

举例说明

假设输入如下：

1
10 2 1

运行过程

1. 初始化：

   • n = 10，m = 2，k = 1。

   • ans = 1，ls = 1，rs = 1。

2. 第一次循环：

   • 更新 ls = (1 - 1) * 2 + 2 = 2。

   • 更新 rs = 1 * 2 + 1 = 3。

   • 检查边界：

     • ls = 2 <= 10，rs = 3 <= 10。

     • 将区间 [2, 3] 的长度 2 加到 ans 中，ans = 3。

3. 第二次循环：

   • 更新 ls = (2 - 1) * 2 + 2 = 4。

   • 更新 rs = 3 * 2 + 1 = 7。

   • 检查边界：

     • ls = 4 <= 10，rs = 7 <= 10。

     • 将区间 [4, 7] 的长度 4 加到 ans 中，ans = 7。

4. 第三次循环：

   • 更新 ls = (4 - 1) * 2 + 2 = 8。

   • 更新 rs = 7 * 2 + 1 = 15。

   • 检查边界：

     • ls = 8 <= 10，rs = 15 > 10。

     • 只计算有效部分 [8, 10] 的长度 3，加到 ans 中，ans = 10。

     • 退出循环。

5. 输出结果：

   • 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 函数输出后序遍历结果。

代码功能分析

1. 输入处理：

   • 读取字符串 s 和整数 n。

   • 字符串 s 从索引 1 开始存储，方便后续处理。

2. FBI树构建：

   • 使用递归方法构建 FBI树。

   • 每个结点的类型由其对应的字符串区间决定。

3. 后序遍历输出：

   • 通过递归方法输出 FBI树 的后序遍历结果。

示例说明

假设输入如下：

3
00111011

运行过程

1. 输入：

   • n = 3，字符串 s = 00111011。

2. 构建 FBI树：

   • 根结点对应整个字符串 00111011，类型为 F。

   • 左子树对应 0011，类型为 F。

   • 右子树对应 1011，类型为 F。

   • 继续递归分割，直到叶子结点。

3. 后序遍历：

   • 遍历顺序：左子树 -> 右子树 -> 根结点。

   • 输出结果：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;
}

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

代码思路分析

1. 递归函数 dfs:

   • 参数:

     • depth: 当前层的深度。

     • start: 当前层的起始索引。

     • N: 数组的总长度。

     • A: 输入的数组。

   • 返回值:

     • 返回一个 pair<int, int>，其中第一个元素是当前层的权值之和，第二个元素是权值之和最大的层数。

   • 递归终止条件:

     • 如果 start >= N，说明已经超出数组范围，返回 {0, depth - 1}，表示上一层的深度。

   • 计算当前层的权值之和:

     • 计算当前层的结束索引 end，并遍历从 start 到 end 的元素，累加得到当前层的权值之和 sum。

   • 递归调用:

     • 递归调用 dfs，计算下一层的权值之和。

   • 比较当前层和下一层的权值之和:

     • 如果当前层的权值之和 sum 大于等于下一层的权值之和，返回当前层的深度 depth。

     • 否则，返回下一层的结果。

2. 主函数 main:

   • 读取输入的数组长度 N 和数组 A。

   • 调用 dfs 函数，从深度 1 开始递归计算。

   • 输出结果，即权值之和最大的层数。

代码优化建议

1. 避免重复计算:

   • 当前代码在每一层都重新计算了当前层的权值之和，可以考虑使用前缀和数组来优化，避免重复计算。

2. 尾递归优化:

   • 递归调用可能会导致栈溢出，可以考虑使用尾递归优化或迭代的方式来实现。

3. 代码可读性:

   • 可以增加一些注释，解释每一部分的逻辑，提高代码的可读性。

优化后的代码示例

#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;
}

优化点解释

1. 前缀和数组:

   • 使用前缀和数组 prefixSum 来快速计算任意区间的和，避免了重复计算。

2. 代码可读性:

   • 增加了注释，解释了每一部分的逻辑，提高了代码的可读性。

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

五、 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）结果，输出二叉树的后序遍历结果。代码的核心思想是通过递归的方式重建二叉树，并在递归过程中输出后序遍历的结果。

代码思路分析

1. 输入处理：

   • 从标准输入读取中序遍历（inor）和前序遍历（pre）的字符串。

2. 递归函数 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 处理左子树和右子树。

   • 输出根节点：

     • 在递归处理完左右子树后，输出根节点，以实现后序遍历（左-右-根）的顺序。

3. 主函数 main：

   • 读取输入的中序遍历和前序遍历字符串。

   • 调用 work 函数开始递归处理。

   • 输出换行符，结束程序。

代码优化建议

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

   • 当前代码在每次递归调用时都会创建新的子字符串，这可能会导致性能问题，尤其是在处理大规模数据时。可以通过传递索引范围来避免字符串拷贝。

2. 使用引用传递参数：

   • 将 pre 和 inor 作为引用传递，避免不必要的拷贝。

3. 增加输入验证：

   • 确保输入的前序遍历和中序遍历是有效的，例如长度一致且包含相同的字符。

优化后的代码示例

#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 - 1
    work(pre, preStart + 1, preStart + leftSize, inor, inStart, k - 1);

    // 递归处理右子树
    // 右子树的前序遍历范围：preStart + leftSize + 1 到 preEnd
    // 右子树的中序遍历范围：k + 1 到 inEnd
    work(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;
}

优化点解释

1. 索引范围传递：

   • 使用 preStart, preEnd, inStart, inEnd 来表示当前处理的范围，避免创建新的子字符串。

2. 引用传递：

   • 将 pre 和 inor 作为 const string& 传递，避免不必要的拷贝。

3. 递归终止条件：

   • 当 preStart > preEnd 或 inStart > inEnd 时，表示当前子树为空，直接返回。

4. 输出根节点：

   • 在递归处理完左右子树后，输出根节点，以实现后序遍历的顺序。

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

评测记录：

六、 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）结果，输出二叉树的前序遍历结果。代码的核心思想是通过递归的方式重建二叉树，并在递归过程中输出前序遍历的结果。

代码思路分析

1. 输入处理：

   • 从标准输入读取中序遍历（inord）和后序遍历（aftord）的字符串。

2. 递归函数 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 处理左子树和右子树。

3. 主函数 main：

   • 读取输入的中序遍历和后序遍历字符串。

   • 调用 beford 函数开始递归处理。

   • 输出换行符，结束程序。

代码优化建议

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

   • 当前代码在每次递归调用时都会创建新的子字符串，这可能会导致性能问题，尤其是在处理大规模数据时。可以通过传递索引范围来避免字符串拷贝。

2. 使用引用传递参数：

   • 将 in 和 after 作为引用传递，避免不必要的拷贝。

3. 增加输入验证：

   • 确保输入的中序遍历和后序遍历是有效的，例如长度一致且包含相同的字符。

优化后的代码示例

#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 - 1
    beford(in, inStart, k - 1, after, afterStart, afterStart + leftSize - 1);

    // 递归处理右子树
    // 右子树的中序遍历范围：k + 1 到 inEnd
    // 右子树的后序遍历范围：afterStart + leftSize 到 afterEnd - 1
    beford(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;
}

优化点解释

1. 索引范围传递：

   • 使用 inStart, inEnd, afterStart, afterEnd 来表示当前处理的范围，避免创建新的子字符串。

2. 引用传递：

   • 将 in 和 after 作为 const string& 传递，避免不必要的拷贝。

3. 递归终止条件：

   • 当 inStart > inEnd 或 afterStart > afterEnd 时，表示当前子树为空，直接返回。

4. 输出根节点：

   • 在递归处理左右子树前，输出根节点，以实现前序遍历的顺序（根-左-右）。

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

评测记录：