P1030 [NOIP 2001 普及组] 求先序排列——题解

解题思路

后序区间的最后一个字符一定是当前子树的根。找到该字符在中序区间中的位置，就能得到左子树结点数，从而把中序、后序区间同时分成左右两部分。先输出根，再递归处理左子树和右子树。

复杂度分析

结点数很小，线性寻找根位置时总复杂度不超过 $O(n^2)$，递归空间 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
string inord, postord;
void work(int il,int ir,int pl,int pr){
    if(il>ir) return;
    char root=postord[pr];
    cout<<root;
    int k=il;
    while(inord[k]!=root) k++;
    int left=k-il;
    work(il,k-1,pl,pl+left-1);
    work(k+1,ir,pl+left,pr-1);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin>>inord>>postord;
    work(0,(int)inord.size()-1,0,(int)postord.size()-1);
    return 0;
}

#include <bits/stdc++.h> using namespace std; string inord, postord; void work(int il,int ir,int pl,int pr){ if(il>ir) return; char root=postord[pr]; cout<<root; int k=il; while(inord[k]!=root) k++; int left=k-il; work(il,k-1,pl,pl+left-1); work(k+1,ir,pl+left,pr-1); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin>>inord>>postord; work(0,(int)inord.size()-1,0,(int)postord.size()-1); return 0; }