PAT 1086

题目 ： Tree Traversals Again

分值 ： 25
难度 ： 中等题
思路 ： 根据题目意思,利用他给的模拟栈操作去构建树,然后去弄出后续遍历
坑点 ： 一开始我把 push的数字当作前序序列(他的确是前序),把pop的数字当作是中序序列(也的确)
       是中序,然后根据前序序列和中序序列去搞出后序序列,用的是自己的小技巧,按照前序序列插入
       比较大小准则则用该对象在中序序列的下标:因为在中序序列中,下标从小到大是 左 中 右 
       因此可以作为插入建树的比较准则 -> 去判断应该插在左子树还是右子树, 但在这题当中因为
       题目特殊性,进来的节点可能是重复的,这就让我这个搜索元素下标的子函数混淆了,他无法标记
       相同元素进入的前后性质.因此是行不通的. 
       故而思索再三,觉得只能够依据它输入的 push 队列和 pop 队列去寻找规律,发现每次push是
       在当前节点下插入一个节点,且遵循先左子树后右子树的特点.而 Pop 则是将一个节点 Pop出去
       如果这个节点被 pop过则继续往上 pop,相当于游标往上移动,换句话说,pop 操作是从一些节点
       往上追溯到下一个插入的节点,所以我在节点结构体中加入 bool pop 表征这个节点是否被pop过
       如果没有,则代表这个节点pop就行,游标停在当前节点,下次如果进来一个push就是对这个节点进
       行插入操作.如果有那么游标就要向上找到第一个没有被pop的父节点来作为下一次push的操作节点.

具体代码如下

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
#include <iostream>
using namespace std;
int flag = 0 ;
typedef struct Node
{
    int self ;
    Node* left ;
    Node* right;
    Node* par ;
    bool pop=false ;
}Nodes ;
Nodes* new_node(int value)
{
    Nodes* temp = (Nodes*) malloc(sizeof(Node));
    temp->self = value ;
    temp->left =NULL ;
    temp->right =NULL ;
    temp->par =NULL ;
    return temp ;
}
void postorder(Nodes *pos)
{
    if(pos!=NULL)
    {
        postorder(pos->left);
        postorder(pos->right);
        if(flag++)
            cout <<" ";
        cout <<pos->self ;
    }
    else return;
}
Nodes *T , *head ,*cur ;
int main()
{
    int N ; cin>>N ;
    string s ;
    int temp ;
    for(int i = 0 ; i< 2*N ;i++)
    {
        cin >>s ;
        if(s[1]=='u')
        {
            cin >> temp ;
            T =new_node(temp) ;
            if(cur==NULL)
            {
                head =T;
                cur =head;
            }
            else {
                if (cur->left == NULL)
                    cur->left = T;
                else cur->right = T;
                T->par = cur;
                cur = T;
            }
        }
        else
        {
            while (cur->pop)
                cur =cur->par ;
            cur->pop =true ;
        }
    }
    postorder(head) ;
}