PAT 1043

题目 ： Is It a Binary Search Tree

分值 ： 25
难度 ： 中等题
思路 ： 插入建树，然后后序遍历，前序遍历，对比一下然后如果OK就输出
坑点 ： 一开始我用的是string，想的是比较时方便一点，然后发现string ‘11’和’2‘哈哈哈.
评语 ： 好久不写二叉搜索树，建树有点子尴尬，69行 Nodes*不赋初值会出现问题.

具体代码如下

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
using namespace std;
typedef struct Node{
    int  self ;
    Node* l;
    Node* r;
}Nodes ;
int temp[1001] ; 
int pre1[10001] ,pre2[10001];
int post1[1001] ,post2[1001] ;
int cur1= 0 ,cur2=0,cur3=0,cur4=0 ; 
Nodes* insert(Nodes* pos , int value )
{                 
    if(pos==NULL)
    {
        Nodes* temp = (Nodes*) malloc(sizeof(Node)) ;
        temp->self= value ;
        temp->l = NULL ;
        temp->r = NULL ;
        return temp ;
    }
    if( pos->self <= value)
        pos->r = insert(pos->r , value);
    else if(pos->self > value)
        pos->l = insert(pos->l , value) ;
    return pos ;

}
void preorder(Nodes* pos)
{
    if(pos)
    {
        pre1[cur1++] = pos->self;
        preorder(pos->l) ;
        preorder(pos->r) ;
    }
}
void pre1order(Nodes* pos)
{
    if(pos)
    {
        pre2[cur2++] = pos->self;
        pre1order(pos->r) ;
        pre1order(pos->l) ;
    }
}

void post1order(Nodes* pos)
{
    if(pos)
    {
        post1order(pos->l);
        post1order(pos->r);
        post1[cur3++] = pos->self;
    }
}
void post2order(Nodes* pos)
{
    if(pos)
    {
        post2order(pos->r);
        post2order(pos->l);
        post2[cur4++] = pos->self;
    }
}
int main() {
    int N ;
    cin>> N ;
    Nodes* head =NULL ;
    for(int i = 0; i< N ;i++)
    {
        cin >> temp[i] ;
        head = insert(head , temp[i] ) ;
    }
    preorder(head);
    pre1order(head);
    int flag1 = 1 ,flag2=1 ;
    for(int i = 0 ; i< N ; i++)
    {   
       //cout << pre2[i]<<" " ;
       if(pre1[i] != temp[i] )
            flag1 = 0 ;
       if(pre2[i] != temp[i] )
            flag2 = 0 ;
    }
    if(flag2 || flag1)
    {
        cout<<"YES"<<endl ;
        if(flag1)
        {
            //cout << "1111"<<endl ;
            post1order(head);
            for(int i = 0 ; i< N ; i++)
            {
                    if(i)
                        cout<<" " ;
                    cout <<post1[i] ;
                }
         }
         else 
         {
            //cout << "2222"<<endl ;
            post2order(head);
            for(int i = 0 ; i< N ; i++)
                {
                    if(i)
                        cout<<" " ;
                    cout <<post2[i] ;
                }
         }
         cout <<endl ;
    }
    else{
        cout <<"NO"<<endl ;
    }
}