1043 Is It a Binary Search Tree

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 
 5 struct Node {
 6     int data;
 7     Node* lchild;
 8     Node* rchild;
 9 } ;
10 
11 vector<int> origin,pre,post;
12 void insert_BST(Node*& root,int data) { //建立BST
13     if(root == NULL) {
14         root = new Node;
15         root->data = data;
16         root->lchild = root->rchild = NULL;
17         return ;
18     }
19     if(data < root->data) insert_BST(root->lchild,data);
20     else insert_BST(root->rchild,data);
21 }
22 void insert_MIBST(Node*& root,int data) {//建立镜像BST
23     if(root == NULL) {
24         root = new Node;
25         root->data = data;
26         root->lchild = root->rchild = NULL;
27         return ;
28     }
29     //不同点 
30     if(data >= root->data) insert_MIBST(root->lchild,data);
31     else insert_MIBST(root->rchild,data);
32 }
33 
34 void preorder(Node* root) { //先序遍历
35     if(root == NULL) return;
36     pre.push_back(root->data);
37     preorder(root->lchild);
38     preorder(root->rchild);
39 }
40 void postorder(Node* root) {//后序遍历
41     if(root == NULL) return;
42     postorder(root->lchild);
43     postorder(root->rchild);
44     post.push_back(root->data);
45 }
46 int main() {
47     int n,data;
48     cin>>n;
49     Node* rootBST = NULL; //定义BST头结点
50     Node* rootMIBST = NULL;//定义MIBST头结点
51     for(int i = 0; i < n; ++i) {
52         cin>>data;
53         origin.push_back(data);
54         insert_BST(rootBST,data);//构造BST 
55         insert_MIBST(rootMIBST,data);//构造镜像BST 
56     }
57     preorder(rootBST);//对BST进行先序遍历
58     if(origin == pre) {
59         printf("YES\n");
60         postorder(rootBST);
61         for(int i = 0; i < post.size(); ++i) {
62             if(i > 0) printf(" ");
63             printf("%d",post[i]);
64         }
65     } else {
66         pre.clear();
67         preorder(rootMIBST);
68         if(origin == pre) {
69             printf("YES\n");
70             postorder(rootMIBST);
71             for(int i = 0; i < post.size(); ++i) {
72                 if(i > 0) printf(" ");
73                 printf("%d",post[i]);
74             }
75         } else
76             printf("NO");
77     }
78     return 0;
79 }