PAT(A) 1086. Tree Traversals Again (25)

原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1086

1086. Tree Traversals Again (25)

---

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Figure 1 Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input: 6 Push 1 Push 2 Push 3 Pop Pop Push 4 Pop Pop Push 5 Push 6 Pop Pop Sample Output: 3 4 2 6 5 1

题目大意

建树，再以后序输出。

解题报告

本题有两种方案： 1. 建树，push就建立实节点，pop就建立空节点，然后后序输出，如后附代码。 2. 可以分析出，push的顺序就是树的先序遍历，出栈顺序就是树的中序遍历，故可以得出数的先序和中序遍历，无需建树，根据先序和中序输出后序。如柳婼题解。题解链接 注意： 1. 若通过建树方案，本题不适用于数组建树，因为最多30个节点，但并不知道树的结构是什么样的，对数组的需求太大。

代码

 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

#include "iostream"
#include "string"
using namespace std;

struct node{
    int data;
    struct node *l;
    struct node *r;
};

typedef struct node * Tree;


int N;
Tree root;
bool first =true;

Tree buildTree(){
    static int cou = 0;
    cou ++;
    if (cou > 2*N)
        return NULL;
    string order;
    cin>>order;
    int t = order.find("sh");
    if(t > -1){
        Tree temp = (Tree)malloc(sizeof(struct node));
        int x;
        cin>>x;
        temp->data = x;
        temp->l = buildTree();
        temp->r = buildTree();
        return temp;
    }
    return NULL;
}

void init(){
    cin>>N;
    root = buildTree();
}

void postOrder(Tree r){
    if(r != NULL){
        postOrder(r->l);
        postOrder(r->r);
        if(first){
            cout<<r->data;
            first = false;
        }else
            cout<<" "<<r->data;
    }
    return;

}

int main(){
    init();
    postOrder(root);
    cout<<endl;
    //system("pause");
}