PAT 1119

题目 ： Pre- and Post-order Traversals

分值 ： 30
难度 ： 难题
思路 ： 前序+后序 求解整棵树是不是唯一的,并给出中序遍历
       前序 :  按照 中左右顺序打印
       后序 :  按照 左右中顺序打印
       解题步骤: 
       1）把后序直接倒序 就变成了 中右左 顺序 我称之为镜像前序
       2）维护一个队列,这个队列 按照 层序建树
       3）镜像前序 和 前序 第一个节点自然是 整棵树的 Root 先把他装入队列顶部
       4）然后依次访问队列顶部元素 在前序队列中找到 该元素的下一个元素 l
          这里分成两种情况
          一）如果 l 已经在队列中,那么舍弃
          二）如果 l 并未出现在队列中,那么添加到队列中,并且作为当前元素的直接左子树
       5）在 镜像前序队列中找到 该元素的下一个元素 r
          这里也分成两种情况
          一）如果 r 已经在队列中,那么舍弃
          二）如果 r 并未出现在队列中,那么添加到队列中,并且作为当前元素的直接右子树
       6）如果 l == r 则说明不能分清楚 该节点到底是在当前节点 左边还是右边 ,因此答案不唯一
       7）依次遍历直至 队列为空 我们就建立起了一颗完整的二叉树 
       8）然后按照 中序遍历顺序打印一下 
坑点 ： 只有一个节点情况了解一下,当出现上述 l==r 情况时 判断一下是不是N==1 因为N==1时
       也会出现 l==r 的情况,但这时是可以确认一棵树的.

具体代码如下

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
#include <iostream>
using namespace std;
int pre[31];
int post[31];
int flag[31] ;
int Q[31];
typedef struct Node
{
    int self;
    int l =0;
    int r =0;
}Nodes ;
Nodes data[31];
bool FLAG =false ;
int h1 , h2 ,old ,temp ;
int print_flag= 0 ;
void inorder(int x)
{
    if(x)
    {
        inorder(data[x].l);
        if(print_flag++)
            cout <<" ";
        cout << x ;
        inorder(data[x].r);
    }
}

int main() {
    int N ;
    cin >> N ;
    for(int i = 0 ; i< N ; i++)
    {
        cin >> temp;
        if(i==0)
            h1 = temp ;
        else
            pre[old] = temp ;
        old = temp ;
    }
    for(int i= 0 ; i< N ; i++)
    {
        cin >> temp ;
        if(i == N-1 )
            h2 = temp ;
        if( i )
            post[temp] = old ;
        old = temp ;
    }
    int cur = 0 , count = 0 ;
    Q[count++ ] = h1 ;
    while(cur < count )
    {
        int now = Q[cur] ;
       // cout << now <<endl ;
        flag[now] = 1 ;
        data[now].self = now ;
        int l = pre[now] ;
        int r = post[now] ;
        if(l == r )
        {
            FLAG = true  ;
          //  cout << now <<" " << l <<" "<<r <<endl ;
            l = 0 ;
        }
        if(l && flag[l]==0) // 子树可用
        {
            flag[l] = 1 ;
            data[now].l  = l ;
            Q[count++] = l ;
        }
        if(r && flag[r]==0)
        {
            flag[r] = 1 ;
            data[now].r  = r ;
            Q[count++] = r ;
        }
        cur ++ ;
    }
    if(!FLAG || N == 1 )
        cout << "Yes"<<endl ;
    else cout <<"No"<<endl ;
    inorder(h1);
    cout <<endl ;
}