樹上問題
===
### 給定前序走訪及中序走訪求後序走訪
例題:[ P1827美国血统](https://www.luogu.com.cn/problem/P1827)

#include<bits/stdc++.h>
using namespace std;
void tree(string pre,string in){
    if(pre.empty()){
        return;
    }
    char root=pre[0];
    int k=in.find(root);
    pre.erase(pre.begin());
    string leftpre=pre.substr(0,k);
    string leftin=in.substr(0,k);
    string rpre=pre.substr(k);
    string rin=in.substr(k+1);
    tree(leftpre,leftin);
    tree(rpre,rin);
    cout<<root;
}
int main(){
    string s1;
    string s2;
    cin>>s1>>s2;
    tree(s2,s1);
}

### 給定中序走訪及後序走訪求前序走訪
例題:[ P1030求先序排列](https://www.luogu.com.cn/problem/P1030)

#include<bits/stdc++.h>
using namespace std;
void build(string post,string in){
    if(post.empty()){
        return;
    }
    char root=post.back();
    int k=in.find(root);
    post.pop_back();
    cout<<root;
    string leftpost=post.substr(0,k);
    string leftin=in.substr(0,k);
    string rightpost=post.substr(k);
    string rightin=in.substr(k+1);
    build(leftpost,leftin);
    build(rightpost,rightin);
}
int main(){
    string s1,s2;
    cin>>s1>>s2;
    build(s2,s1);
}

### 給定前序走訪及後序走訪求中序走訪個數
例題:[ P1229遍历问题](https://www.luogu.com.cn/problem/P1229)

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s1,s2;
    cin>>s1>>s2;
    int ans=0;
    int len=s1.size();
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            if(s1[i]==s2[j]&&s1[i+1]==s2[j-1]&&i!=len-1){
                ans++;
            }
        }
    }
    cout<<(1<<ans);
}

###　給定中序走訪及層序走訪求前序走訪
例題:(https://www.luogu.com.cn/problem/U167766)

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
string s1,s2;
void build(int l1,int r1,int l2,int r2){
    int i,j,b;
    for(i=l2;i<=r2;i++){
        b=0;
        for(j=l1;j<=r1;j++){
            if(s2[i]==s1[j]){
                b=1;
                cout<<s1[j];
                break;
            }
        }
        if(b){
            break;
        }
    }
    if(j>l1){
        build(l1,j-1,l2,r2);
    }
    if(j<r1){
        build(j+1,r1,l2,r2);
    }
}
int main()
{
    cin>>s1>>s2;
    build(0,s1.length()-1,0,s2.length()-1);
    return 0;
}