1043. Is It a Binary Search Tree (25)

题目连接：https://www.patest.cn/contests/pat-a-practise/1043

今天难道是我状态不佳？……

思路很清晰，以两种规则建树，分别得到其前序数组，和原始数组进行比较，若有相等的则将该树后序遍历输出。

遗忘和不熟悉的知识点：BST（搜索树）及相关如插入操作等；vector变量之间可以进行比较。

  1 #include<stdio.h>
  2 #include<vector>
  3 #include<stdlib.h>
  4 #define MAXN 1005
  5 using namespace std;
  6 typedef struct TNode{
  7     int Data;
  8     struct TNode*Left;
  9     struct TNode*Right;
 10 }BT;
 11 int N;
 12 
 13 BT* Insert1(BT* T1,int x)
 14 {
 15     if (!T1)
 16     {
 17         T1=(BT*)malloc(sizeof(struct TNode));
 18         T1->Data=x;
 19         T1->Left=T1->Right=NULL;
 20     }
 21     else
 22     {
 23         if (x>=T1->Data)T1->Right=Insert1(T1->Right,x);
 24         else if (x<T1->Data)T1->Left=Insert1(T1->Left,x);
 25     }
 26     return T1;
 27 }
 28 
 29 BT* Insert2(BT* T2,int x)
 30 {
 31     if (!T2)
 32     {
 33         T2=(BT*)malloc(sizeof(struct TNode));
 34         T2->Data=x;
 35         T2->Left=T2->Right=NULL;
 36     }
 37     else
 38     {
 39         if (x>=T2->Data)T2->Left=Insert2(T2->Left,x);
 40         else if (x<T2->Data)T2->Right=Insert2(T2->Right,x);
 41     }
 42     return T2;
 43 }
 44 
 45 void Perorder(BT*T,vector<int>&v)
 46 {
 47     if (T)
 48     {
 49         v.push_back(T->Data);
 50         Perorder(T->Left,v);
 51         Perorder(T->Right,v);
 52     }
 53 }
 54 
 55 void Postorder(BT*T,vector<int>&v)
 56 {
 57     if (T)
 58     {
 59         Postorder(T->Left,v);
 60         Postorder(T->Right,v);
 61         v.push_back(T->Data);
 62         //printf("%d ",T->Data);
 63     }
 64 }
 65 
 66 void Out(BT *T,vector<int>&v)
 67 {
 68     Postorder(T,v);
 69     int i;
 70     for (i=0;i<N;i++)
 71     {
 72     if (i==0)printf("%d",v[i]);
 73     else printf(" %d",v[i]);
 74     }
 75 }
 76 int main()
 77 {
 78     int i,v;
 79     vector<int>v1,v2,v3,ans;
 80     scanf("%d",&N);
 81     for (i=0;i<N;i++){scanf("%d",&v);v1.push_back(v);}
 82     BT*T1,*T2;
 83     T1=T2=NULL;
 84 
 85     for (i=0;i<N;i++)
 86     {
 87         T1=Insert1(T1,v1[i]);
 88         T2=Insert2(T2,v1[i]);
 89     }
 90     Perorder(T1,v2);
 91     Perorder(T2,v3);
 92     if (v1!=v2 &&v1!=v3)
 93     {
 94         printf("NO");
 95         return 0;
 96     }
 97     else
 98     {
 99         printf("YES
");
100         if (v1==v2)Out(T1,ans);
101         else if (v1==v3)Out(T2,ans);
102     }
103     return 0;
104 }