PATest 2017春季 ZigZagging on a Tree (30) 题解

1127. ZigZagging on a Tree (30)

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” — that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1

Sample Output:

1 11 5 8 17 12 20 15

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
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
int n;
int postorder[31],inorder[31];
struct node{
    int data;
    node * left;
    node * right;
};
void MakeTree(int post_start,int post_end,int in_start,int in_end,node * CURRENT){
    CURRENT->data=postorder[post_end];
    if(post_start>post_end||in_start>in_end){
        CURRENT->data=-1;
        CURRENT->left=NULL;
        CURRENT->right=NULL;
        return;
    }
    else if(post_start==post_end&&in_start==in_end){
        CURRENT->left=NULL;
        CURRENT->right=NULL;
        return;
    }
    node * left=new node;
    node * right=new node;
    CURRENT->left=left;
    CURRENT->right=right;
    int pos;
    for(int i=in_start;i<=in_end;i++){
        if(inorder[i]==postorder[post_end]){
            pos=i;
            break;
        }
    }
    MakeTree(post_start,post_start+pos-1-in_start,in_start,pos-1,left);
    MakeTree(post_start+pos-in_start,post_end-1,pos+1,in_end,right);
}
void level_Order(node * ROOT){
    queue<node *> Q;
    Q.push(ROOT);
    while(!Q.empty()){
        node * cur=Q.front();
        Q.pop();
        if(cur==NULL||cur->data==-1)continue;
        cout<<cur->data<<" ";
        Q.push(cur->left);
        Q.push(cur->right);
    }
}
void ZigZagging_Order(node * ROOT){
    deque<node *> Q;
    deque<node *> S;
    bool first=true;
    S.push_front(ROOT);
    bool flag=false;//true为队列,false为栈
    while(!(Q.empty()&&S.empty())){
        node * cur;
        if(flag==true){//队列
            cur=Q.front();
            Q.pop_front();
            if(!first){
                cout<<" ";
            }else{
                first=false;
            }
            cout<<cur->data;
            if(cur->left!=NULL&&cur->left->data!=-1)S.push_front(cur->left);
            if(cur->right!=NULL&&cur->right->data!=-1)S.push_front(cur->right);
            if(Q.empty())flag=false;
        }else{//栈
            cur=S.front();
            S.pop_front();
            if(!first){
                cout<<" ";
            }else{
                first=false;
            }
            cout<<cur->data;
            if(cur->left!=NULL&&cur->right->data!=-1)Q.push_front(cur->right);
            if(cur->right!=NULL&&cur->left->data!=-1)Q.push_front(cur->left);
            if(S.empty())flag=true;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>inorder[i];
    }
    for(int i=1;i<=n;i++){
        cin>>postorder[i];
    }
    node * ROOT=new node;
    MakeTree(1,n,1,n,ROOT);
    ZigZagging_Order(ROOT);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注