PTA A_1086 Tree Traversals Again

798236606

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805380754817024

解：
前序遍历+中序遍历 恢复二叉树
Push的顺序是前序遍历
Pop的顺序是中序遍历

1. #include<cstdio>
   
2. #include<cstring>
   
3. 
   
4. typedef struct node{
   
5.     int data;
   
6.     struct node *lchild, *rchild;
   
7. 
   
8.     node(){
   
9.         lchild = rchild = NULL;
   
10.     }
    
11. } BTNode, *BTREE;
    
12. 
    
13. int n, num, preorder[35], inorder[35];
    
14. 
    
15. void input(void)
    
16. {
    
17.     int stack[35], top = -1, pi = 0, ii = 0;;
    
18.     char s[5];
    
19. 
    
20.     scanf("%d", &n);
    
21.     for (int i = 0; i < 2 * n; i++)
    
22.     {
    
23.         scanf("%s", s);
    
24. 
    
25.         if (strcmp(s, "Push"))
    
26.             inorder[ii++] = stack[top--];
    
27.         else
    
28.         {
    
29.             scanf("%d", preorder + pi);
    
30.             stack[++top] = preorder[pi++];
    
31.         }
    
32.     }
    
33. }
    
34. 
    
35. int find(int target)
    
36. {
    
37.     for (int i = 0; i < n; i++)
    
38.         if (inorder[i] == target)
    
39.             return i;
    
40. }
    
41. 
    
42. void insert(BTREE root, int pos)
    
43. {
    
44.     if (!root) return;
    
45. 
    
46.     int parents = find(root->data);
    
47. 
    
48.     if (pos > parents)
    
49.     {
    
50.         if (root->rchild)
    
51.             insert(root->rchild, pos);
    
52.         else
    
53.         {
    
54.             root->rchild = new BTNode;
    
55.             root->rchild->data = inorder[pos];
    
56.         }
    
57.     }
    
58.     else
    
59.     {
    
60.         if (root->lchild)
    
61.             insert(root->lchild, pos);
    
62.         else
    
63.         {
    
64.             root->lchild = new BTNode;
    
65.             root->lchild->data = inorder[pos];
    
66.         }
    
67.     }
    
68. }
    
69. 
    
70. void print_postorder(BTREE root)
    
71. {
    
72.     if (!root) return;
    
73. 
    
74.     print_postorder(root->lchild);
    
75.     print_postorder(root->rchild);
    
76.     printf("%d", root->data);
    
77. 
    
78.     if (++num < n) putchar(' ');
    
79. }
    
80. 
    
81. int main(void)
    
82. {
    
83.     input();
    
84. 
    
85.     BTREE root = new BTNode;
    
86.     root->data = preorder[0];
    
87.     for (int i = 1; i < n; i++)
    
88.         insert(root, find(preorder[i]));
    
89. 
    
90.     print_postorder(root);
    
91. 
    
92.     return 0;
    
93. }

复制代码