PAT 1020

题目 ： Tree Traversals

分值 ： 25
难度 ： 中等题
思路 ： 后续遍历倒过来按照中序遍历下标作为大小准则插入建树，然后层序遍历。
坑点 ： 58行 貌似PAT的g++版本对于 指针型动态数组不是很OK啊，段错误。搞得我懵逼了一下。
评语 ： 思路很清晰，抓住中序是个好东西就好了，这种题，回顾了一下建树操作。

具体代码如下

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
using namespace std ;
typedef struct Node
{
    int self ;
    int index ;
    Node* left ;
    Node* right ;
}Nodes ;
Nodes list[31] ;
int data[31];
int data2[31] ;
int N ;
int find( int value)
{
    for(int i = 0 ; i< N;i++)
    {
        if(data2[i] == value)
            return i ;
    }
}
Nodes* insert(Nodes* pos , int value )
{
    int index = find(value);
    if(!pos)
    {
        Nodes* temp = (Nodes*) malloc(sizeof(Node)) ;
        temp->left = NULL ;
        temp->right =NULL  ;
        temp->self = value ;
        temp->index =index ;
        return temp ;
    }
    if(pos->index < index )
    {
        pos->right = insert(pos->right , value );
    }
    else if(pos->index > index)
    {
        pos->left = insert(pos->left , value ) ;
    }
    return pos;

}

int main() {

    cin >> N ;
    Nodes* head ;
    for(int i = 0 ; i< N ;i++)
        cin>> data[i] ;
    for(int i = 0 ; i < N; i++)
        cin>> data2[i] ;
    for(int i = N-1 ; i>=0 ;i--)
    {
        head = insert( head , data[i]);
    }
    Nodes* Q[31] ;
    int cur = 0 ;
    int count = 0 ;
    Q[count++] = head ;
    while(cur <count)
    {
        if(Q[cur]->left!=NULL)
            Q[count ++ ] = Q[cur]->left ;
        if(Q[cur]->right!= NULL)
            Q[count ++] = Q[cur]->right ;
        if(cur)
            cout<<" ";
        cout << Q[cur]->self;
        cur++ ;
    }
    cout <<endl ;
    return 0;

}