PAT 1127

题目 ： ZigZagging on a Tree

分值 ： 30
难度 ： 中等题
思路 ： 利用中序 和后序遍历 建树,然后自定义规则 遍历 
坑点 ： 中序后序遍历,用自定义的下标插入法即可,为了实现他所说的规则遍历,我的解决方案是
       1）先按照层序遍历得出层序遍历数组;
       2）然后按照 层数第一关键字升序;
       3）偶数层下标第二关键字降序(从右到左)
       4）奇数层下标第二关键字升序(从左到右)
       5) 最后输出

具体代码如下

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
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <algorithm>
using namespace std ;
int N ;
int inorder[31];
int postorder[31];
typedef struct Node
{
    int self ;
    int index ;
    int level ;
    Node* l ;
    Node* r ;
}Nodes;
Node* Q[31] ;
int find_index(int x )
{
    for(int i = 0 ; i< N ; i++)
    {
        if(inorder[i] == x)
            return i ;
    }
}
Node* insert(Node* pos , int x)
{
    if(pos==NULL)
    {
        Node* temp =(Node*)malloc(sizeof(Node)) ;
        temp -> self = x ;
        temp -> index = find_index(x) ;
        temp -> l = NULL ;
        temp -> r = NULL ;
        return temp ;
    }
    int current = find_index(x) ;
    if(current <= pos->index )
        pos->l = insert(pos->l , x) ;
    if(current > pos->index)
        pos->r = insert(pos->r , x );
    return pos ;
}
bool cmp(Node* a , Node* b )
{
    if(a->level == b->level)
    {
        if(a->level%2 == 0 ) //偶数行
            return a->index > b-> index ;
        if(a->level%2 == 1 )
            return a->index < b-> index ;
    }
    else return a->level < b->level ;
}
int main() {
    cin >> N ;
    Node* head = NULL  ;
    for(int i = 0 ; i< N ; i++)
        cin >> inorder[i] ;
    for(int i = 0 ; i< N ; i++)
        cin >> postorder[i] ;
    for(int i = N-1 ; i>= 0 ; i--)
    {
        head = insert(head , postorder[i]) ;
    }
    int count = 0 , cur = 0 ;
    Q[count] = head ;
    Q[count++]->level = 0 ;
    while(cur < count )
    {
        int old = Q[cur]->level ;
        if(Q[cur]->l)
        {
            Q[count] = Q[cur]->l ;
            Q[count++]->level = old + 1 ;
        }
        if(Q[cur]->r)
        {
            Q[count] =Q[cur]->r ;
            Q[count++]->level = old +1 ;
        }
        cur ++ ;
    }
    sort(Q,Q+cur,cmp);
    for(int i = 0 ; i< cur ; i++)
    {
        if(i)
            cout <<" ";
        cout << Q[i]->self ;
    }
}