hdu 1710恢复二叉树

恢复二叉树是面试的经典题目，

首先我们知道的结论是已知前序和中序或者后序和中序，那么我们就可以唯一的确定一个二叉树。

思路是在  中序的某一段中  前序（后序）中靠前（后）的 节点是这一段中序的父亲节点，并且由这个节点将这一段划分为二。。当不能划分的时候就是到了叶子节点。

所以我们可以考虑传递父亲节点和他的部分儿子，再在这一些节点里面找到一个父亲。。这样就可以递归解决问题。

PS。很简单的思路，但是由于手残加脑残，写了不少时间，下面是ac代码。。蒟蒻加油！

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
using namespace std;

int n;
int mid[1005];
int first[1005];
int vis[1005];
int has[1005];
vector<int> son[1005];

void sl(int fa,int l,int r){
    if(r<l) return;
    if(r==l){
        son[fa].push_back(mid[l]);
        return;
    }
    int mi=999999,index=0;
    for(int i=l;i<=r;i++){
        if(has[mid[i]]<mi){
             mi=has[mid[i]],index=i;
        }
    }
    son[fa].push_back(mid[index]);

    sl(first[mi],index+1,r);
    sl(first[mi],l,index-1);
}
vector<int> ans;
void dfs(int x){
    for(int i=son[x].size()-1;i>=0;i--)
        dfs(son[x][i]);
    ans.push_back(x);
}


int main()
{
    while(cin>>n){
        memset(vis,0,sizeof(vis));
        ans.clear();
        for(int i=0;i<1005;i++) son[i].clear();
        for(int i=0;i<n;i++) cin>>first[i];
        for(int i=0;i<n;i++) cin>>mid[i];
        for(int i=0;i<n;i++) has[first[i]]=i;

        sl(0,0,n-1);
        dfs(first[0]);
        for(int i=0;i<n;i++){
            cout<<ans[i];
            if(i!=n-1) cout<<" ";
            else cout<<endl;
        }
    }
    return 0;
}