Problem Solving►UVa

UVa 536 - Tree Recovery

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

網路上教學蠻多的。
可參考 Uva 548 的做法。

這邊不用真的建一棵樹出來，以後序的方式建構樹，印每個子樹的根節點，即為後序(從左子樹開始處理)。

Code

UVa 536
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

char pre[27], in[27];
void buildTree(int in_start, int in_end, int pre_idx);
void post(int idx);
int main()
{
    while (scanf("%s%s", pre, in) != EOF)
    {
        int len = strlen(pre);
        buildTree(0, len, 0);
        putchar('\n');
    }

    return 0;
}
void buildTree(int in_start, int in_end, int pre_idx)
{
    if (in_start >= in_end)
        return;

    int pos = find(in + in_start, in + in_end, pre[pre_idx]) - in;//根節點

    int lLen = pos - in_start;//左子樹內點的個數

    buildTree(in_start, in_start + lLen, pre_idx + 1);//左子樹
    buildTree(pos + 1, in_end, pre_idx + lLen + 1);//右子樹

    putchar(in[pos]);//後序印出
}