PTA A_1043 Is It a Binary Search Tree

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805440976633856

解：
二叉搜索树的插入序列=前序遍历

1. #include<cstdio>
   
2. #include<vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. typedef struct node{
   
7.     int data;
   
8.     struct node *left, *right;
   
9. } BSTNode, *BSTree;
   
10. 
    
11. vector<int> insert_list, preorder_list;
    
12. int n;
    
13. 
    
14. bool mirror(int a, int b, bool flag)
    
15. {
    
16.     if (flag) return a < b;
    
17. 
    
18.     return a >= b;
    
19. }
    
20. 
    
21. void insert(BSTree &T, int temp, bool flag)
    
22. {
    
23.     if (!T)
    
24.     {
    
25.         T = new BSTNode;
    
26.         T->data = temp;
    
27.         T->left = T->right = NULL;
    
28.     }
    
29.     else
    
30.         mirror(temp, T->data, flag) ? insert2(T->left, temp, flag) : insert2(T->right, temp, flag);
    
31. }
    
32. 
    
33. void preorder(BSTree T)
    
34. {
    
35.     if (T)
    
36.     {
    
37.         preorder_list.push_back(T->data);
    
38.         preorder(T->left);
    
39.         preorder(T->right);
    
40.     }
    
41. }
    
42. 
    
43. void postorder(BSTree T)
    
44. {
    
45.     if (T)
    
46.     {
    
47.         postorder(T->left);
    
48.         postorder(T->right);
    
49.         printf("%d", T->data);
    
50.         if (--n) putchar(' ');
    
51.     }
    
52. }
    
53. 
    
54. int main(void)
    
55. {
    
56.     BSTree T1 = NULL, T2 = NULL;
    
57. 
    
58.     scanf("%d", &n);
    
59.     for (int i = 0; i < n; i++)
    
60.     {
    
61.         int temp;
    
62. 
    
63.         scanf("%d", &temp);
    
64.         insert(T1, temp, false);
    
65.         insert(T2, temp, true);
    
66.         insert_list.push_back(temp);
    
67.     }
    
68. 
    
69.     preorder(T1);
    
70. 
    
71.     if (preorder_list == insert_list)
    
72.     {
    
73.         puts("YES");
    
74.         postorder(T1);
    
75.     }
    
76.     else
    
77.     {
    
78.         preorder_list.clear();
    
79.         preorder(T2);
    
80. 
    
81.         if (preorder_list == insert_list)
    
82.         {
    
83.             puts("YES");
    
84.             postorder(T2);
    
85.         }
    
86.         else
    
87.             puts("NO");
    
88.     }
    
89. 
    
90.     return 0;
    
91. }

复制代码