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

题目链接：https://www.luogu.com.cn/problem/P1030

题目大意

给定一棵二叉树的 中序遍历 和 后序遍历 序列（每个节点用不同的大写字母表示，节点数 ≤ 8），要求输出该二叉树的 先序遍历 序列。

解题思路

1. 三种遍历的特点回顾

• 先序遍历（Preorder）：根 → 左子树 → 右子树
• 中序遍历（Inorder）：左子树 → 根 → 右子树
• 后序遍历（Postorder）：左子树 → 右子树 → 根

关键性质：

• 后序遍历的最后一个元素 一定是当前子树的 根节点
• 在 中序遍历中找到该根的位置，其左边是左子树，右边是右子树
• 利用这个划分，可以递归地重建整棵树，并直接输出先序序列（根左右）

由于题目只要求输出先序序列，不需要真正建树，只需在递归过程中按“根→左→右”的顺序输出即可。

2. 递归策略

定义函数 beford(in, after)：

• in：当前子树的中序序列
• after：当前子树的后序序列

步骤如下：

1. 如果序列为空，直接返回（递归边界）
2. 取 after 的最后一个字符 ch —— 这是当前子树的根
3. 输出 ch（这就是先序遍历的当前节点）
4. 在 in 中找到 ch 的位置 kin[0..k-1] 是左子树的中序in[k+1..end] 是右子树的中序
5. 根据左子树长度 k，划分 after：左子树后序：after[0..k-1]（共 k 个字符）右子树后序：after[k..end-1]（跳过最后一个根）
6. 递归处理左子树、右子树

注意：后序中，左子树占前 k 个，右子树占接下来的 len - k - 1 个（最后一个是根）。

代码解析

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

        // 递归左子树：中序 [0, k)，后序 [0, k)
        beford(in.substr(0, k), after.substr(0, k));

        // 递归右子树：中序 [k+1, end)，后序 [k, end-1)
        beford(in.substr(k + 1), after.substr(k, in.size() - k - 1));
    }
}

int main() {
    string inord, aftord;
    cin >> inord >> aftord;
    beford(inord, aftord);
    cout << endl;
    return 0;
}

关键点说明：

• in.substr(0, k)：从位置 0 开始取 k 个字符（左子树中序）
• after.substr(0, k)：左子树后序，长度也为 k
• in.substr(k + 1)：从 k+1 到末尾（右子树中序）
• after.substr(k, in.size() - k - 1)：起始位置 k长度 = 总长 - 左子树长 - 根 = in.size() - k - 1

因为中序和后序长度始终相等，所以可以用 in.size() 代表当前子树节点数。

复杂度分析

• 节点数 n <= 8
• 每次递归调用 find 和 substr，最坏时间复杂度 O(n^2)
• 空间复杂度 O(n)（递归栈 + 字符串拷贝）
• 对于 n <= 8，效率完全足够

总结

本题是经典的根据两种遍历重建二叉树问题。核心在于：

• 利用后序确定根
• 利用中序划分左右子树
• 递归过程中直接按先序顺序输出

无需显式建树，简洁高效，是理解树遍历关系的典型例题。