UVA - 10410 Tree Reconstruction (根据dfs序和bfs序恢复一颗树)

题意：

分析：

这题一开始完全没有思路， 一直没有找出规律。

参考了http://www.cnblogs.com/Wade-/p/6358859.html 和 http://www.cnblogs.com/jerryRey/p/4622927.html

在dfs序列中，相邻的两个结点u，v之间(dfs_pos(u) + 1 =  dfs_pos(v))，有父子，兄弟，其他3种关系。

父子关系：在bfs中u，v并不是相邻， bfs_pos(v) > bfs_pos(u) ， 那么u为v父亲， v为u儿子。

兄弟关系：在bfs中, bfs(u) + 1 = bfs(v) (相邻).

其他关系：其实就是没有关系， bfs_pos(u) >= bfs_pos(v)

只要知道这3个关系， 就可以找出每个节点的父亲了， 用栈去模拟

#include <bits/stdc++.h>

using namespace std;

vector<int> son[];

int n;

int pos[];

int main(){

    while(~scanf("%d", &n)){

        for(int i = ; i < n; i++){

            int t;

            scanf("%d", &t);

            pos[t] = i;

        }

        stack<int> s;

        int root;

        scanf("%d", &root);

        s.push(root);

        for(int i = ; i < n - ;i++){

            int x;

            scanf("%d", &x);

            for(;;){

                int u = s.top();

                if(pos[u] +  < pos[x] || u == root){//如果u与x不相邻而且pos(x) > pos(u)(bfs中序列， 根除外)

                    son[u].push_back(x);            // 那么u一定是x的父亲

                    s.push(x);

                    break;

                }

                else{

                    s.pop();

                }

            }

        }

        for(int i = ; i <= n; i++){

            printf("%d:", i);

            sort(son[i].begin(), son[i].end());

            for(int j = ; j < son[i].size(); j++){

                printf(" %d", son[i][j]);

            }

            son[i].resize();

            puts("");

        }

    }

}