P1827 [USACO3.4] 美国血统 American Heritage——题解

解题思路

前序区间第一个字符是根。它在中序区间中的位置把结点分成左右子树，并确定两棵子树在前序序列中的长度。递归输出左子树、右子树，最后输出根，便得到后序遍历。

复杂度分析

线性查找根位置时，时间复杂度 $O(n^2)$，递归空间 $O(n)$。

C++17 参考代码

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

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