题解：P1030 [NOIP2001 普及组] 求先序排列

niuniudundun · 2025-01-27 09:17:21 · 题解

题目传送门

题目大意

给出一棵二叉树的中序与后序排列。求出它的先序排列。

解法

一些常识：

• 后序遍历中最后一个遍历根，那么最后一个就是根。

• 中序遍历可以通过找根获得左右子树。

设中序遍历为 mid，后序遍历为 pos。

使用递归，先找到后序遍历最后一个字符 pos_{l-1}（l 是 pos 长度），这个就是根，输出他，在 mid 中找到这个根，设位置为 p，随后将 mid 拆成两半（根不要）[0,p),[p+1,l)（这里 l 是 mid 长度），pos 拆为 [0,p),[p,l-p-1)，随后遍历这两个子串，到 mid 长度小于 0。

因为所有节点只遍历一次，复杂度 O(n+\alpha)，n 是节点数，\alpha 是字符串函数 \texttt{find},\texttt{substr} 常数。

代码：

#include<iostream>
using namespace std;
string mid,pos;//中序，后序
void pre(string mid,string pos){
    if(mid.length()>0){
        int l=pos.length();
        char a=pos[l-1];
        cout<<a;
        int p=mid.find(a);
        pre(mid.substr(0,p),pos.substr(0,p));
        pre(mid.substr(p+1),pos.substr(p,mid.length()-p-1));
    }
} 
int main(){
    cin>>mid>>pos;
    pre(mid,pos);
    return 0;
}