Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem H: Tree Reconstruction

You have just finished a compiler design homework question where you had to find the parse tree of an expression. Unfortunately you left your assignment in the library, but luckily your friend picked it up for you. Instead of e-mailing you the parse tree so that you can rewrite the solution, your friend decides to play a practical joke and sends you just the DFS and BFS trace. Rather than try to redo the entire question you decide to reconstruct the tree.

Input

The input file contains several test cases as described below.

The first line of a input is the number n (1 <= n <= 1000) of nodes in the tree. The nodes in the tree are numbered 1, 2, ..., n. The remaining numbers are the BFS traversal followed by the DFS traversal. Note that when a parent was expanded the children were traversed in ascending order.

Output

The output for each case should consist of n lines, one for each node. Each line should start with the node number followed by a colon followed by a list of children in ascending order. If there is more than one solution, any correct answer is acceptable.

Sample Input

8
4 3 5 1 2 8 7 6
4 3 1 7 2 6 5 8

Sample Output

1: 7
2: 6
3: 1 2
4: 3 5
5: 8
6:
7:
8:

---

Problem Setter: Jonathan Backer

還第一遇到這種給 BFS 順序跟 DFS 順序的題目，
而且還會是多組解，而且不一定是二分樹。

至於要怎麼輸出一組解，我決定用遞迴去切割，根據 BFS 的順序。

舉個範例輸入：
root = 4

3 5 1 2 8 7 6
3 1 7 2 6 5 8

會發現 3 5 是 4 的 son child, 接著將 dfs 的順序切割出來
root = 3

1 2 8 7 6
1 7 2 6

會發現 1 2 是 3 的 son child, 繼續做切割。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int BFS[1005], DFS[1005];
int n;
vector<int> g[1005];
vector<int> sub_dfs[1005];
int root[1005];
int dfs(int nd, int &bidx) {
    /*printf("%d %d:\n", nd, bidx);
    for(int i = 0; i < sub_dfs[nd].size(); i++)
        printf("%d ", sub_dfs[nd][i]);
    puts("");*/
    int i, x;
    for(i = 0; i < sub_dfs[nd].size(); i++) {
        if(sub_dfs[nd][i] == BFS[bidx] && bidx < n) {
            x = BFS[bidx];
            g[nd].push_back(x);
            root[x] = nd;
            bidx++, i++;
            while(bidx < n && i < sub_dfs[nd].size()) {
                if(sub_dfs[nd][i] == BFS[bidx])
                    break;
                sub_dfs[x].push_back(sub_dfs[nd][i]);
                root[sub_dfs[nd][i]] = x;
                i++;
            }
            i--;
        }
    }
    while(bidx < n)
        dfs(root[BFS[bidx]], bidx);
}
void print(int n) {
    int i, j;
    for(i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
        printf("%d:", i);
        for(j = 0; j < g[i].size(); j++)
            printf(" %d", g[i][j]);
        puts("");
    }
}
int main() {
    int i;
    while(scanf("%d", &n) == 1) {
        for(i = 0; i < n; i++)
            scanf("%d", &BFS[i]);
        for(i = 0; i < n; i++)
            scanf("%d", &DFS[i]);
        for(i = 0; i <= n; i++)
            g[i].clear(), sub_dfs[i].clear();
        for(i = 1; i < n; i++)
            sub_dfs[BFS[0]].push_back(DFS[i]);
        int bidx = 1;
        dfs(BFS[0], bidx);
        print(n);
    }
    return 0;
}
/*
8
4 3 5 1 2 8 7 6
4 3 1 7 2 6 5 8
*/