投資錢景>買台積電就對了來自星星的你也會打廣告?正妹的東京自助旅行老伯送飲料 遭學生糾察...
2012-06-02 17:52:11 人氣(338) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 10701 - Pre, in and post

0
收藏
0
推薦

Problem F - Pre, in and post

Time Limit: 1 second

A common problem in data structures is to determine the traversal of a binary tree. There are three classic ways to do it:

Pre-order: You must visit in sequence the root, left subtree and the right subtree.
In-order: You must visit in sequence the left subtree, the root and the right subtree.
Post-order: You must visit in sequence the left subtree, the right subtree and the root.

See the picture below:

graph.png

The pre, in and post-order traversal are, respectively,  ABCDEF, CBAEDF and CBEFDA. In this problem, you must compute the post-order traversal of a binary tree given its in-order and pre-order traversals.

Input

The input set consists of a positive number C ≤ 2000, that gives the number of test cases and C lines, one for each test case. Each test case starts with a number 1 ≤ N ≤ 52, the number of nodes in this binary tree. After, there will be two strings S1 and S2 that describe the pre-order and in-order traversal of the tree. The nodes of the tree are labeled with different characters in the range a..z and A..Z. The values of N, S1 and S2 are separeted by a blank space.

Output

For each input set, you should output a line containing the post-order transversal for the current tree.

Sample input

3
3 xYz Yxz
3 abc cba
6 ABCDEF CBAEDF

Sample output

Yzx
cba
CBEFDA


這東西很久沒寫, 都快忘光了

#include <stdio.h>
char a[60], b[60];
int idx;
void find(int l, int r) {
    if(l > r)   return;
    int i;
    for(i = l; i <= r; i++) {
        if(b[i] == a[idx])
            break;
    }
    if(i != r+1) {
        idx++;
        find(l, i-1);
        find(i+1, r);
        putchar(b[i]);
    }
}
int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %s %s", &n, a, b);
        idx = 0;
        find(0, n-1);
        puts("");
    }
    return 0;
}

10701Prein and post
台長:Morris
人氣(338) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][最大生成樹] 1234 - RACING
此分類上一篇:[UVA][中國郵���問題] 117 - The Postal Worker Rings Once

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文