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:

1
2
3
4
5
6
7
8
9
10
11
12
13
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

1
3 4 2 6 5 1

代码实现

C语言

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/*
本题本质上是已知前序中序遍历，求后序遍历的问题。
在输入的时候有如下规律：
1、第一个push进来的是整个树的根节点。
2、若本次操作为push，且上次操作为push，则本次push的节点是上次push节点的左儿子。
3、若本次操作为push，且上次操作为pop，则本次push节点是上次pop出来节点的右儿子。
4、若本次操作为pop，且上次操作为push，则本次push节点是叶节点。
5、若本次操作为pop，且上次操作为pop，无节点设置。 
*/

#include<stdio.h>
#include<string.h>
#define MaxTree 30
#define Null -1

int A[MaxTree];	// 用于记录递归后序遍历得到的节点号 
int Aindex = 0;

struct TreeNode {
	int Left;
	int Right;
} T[MaxTree];

struct Stack {
	int TreeNodes[MaxTree];
	int front;
} S;

void InitStack() {
	for ( int i=0; i<MaxTree; i++ ) {
		S.TreeNodes[i] = Null;
	}
	S.front = MaxTree;
}

void InitTree() {
	for ( int i=0; i<MaxTree; i++ ) {
		T[i].Left = Null;
		T[i].Right = Null;
	}
}

void Push(int R) {
	if ( S.front ) {
		S.front--;
		S.TreeNodes[S.front] = R;
	} else {
		printf("Stack full\n");
	}
}

int Pop() {
	int output;
	if ( S.front < MaxTree ) {
		output = S.TreeNodes[S.front];
		S.front++;
		return output;
	} else {
		printf("Stack empty");
	}
}

void PostOrderTraversal(int Root) {	
	if ( Root!=Null ) {
		PostOrderTraversal(T[Root].Left);
		PostOrderTraversal(T[Root].Right);
		A[Aindex++] = Root;		// 递归后序遍历需要一个全局变量储存得到的节点号 
	}
}

int main() {
	int N;	// 输入的节点数 
	int Root;	// 标记整个树的根节点 
	int RootFlag = 0;	// 标记整个树的根节点是否已存在 
	int record = 0;	// 记录每次push和pop的节点 
	int pushpop = 1;	// 记录上次操作，1代表push，0代表pop 
	InitTree();
	InitStack();

	scanf("%d", &N);	
	for ( int i=0; i<2*N; i++ ) {
		char operation[10]; 
		int R;
		scanf("%s", operation);
		if ( strcmp(operation, "Push") == 0 ) { // 本次操作push 
			scanf("%d", &R);
			if ( RootFlag ) {	// 整个树根节点已存在时 
				if ( pushpop == 1 ) {	// 右儿子 
					T[record].Left = R;
				} else if ( pushpop == 0 ) {	// 左儿子 
					T[record].Right = R;
				}
			} else {	// 整个树根节点不存在时
				Root = R;   // 记录整个树的根节点
				RootFlag = 1;				 
			}
			Push(R);
			record = R;	// 操作完成后更新记录节点为本次节点 
			pushpop = 1;	// 更新操作状态为push 
		} else {	// 本次操作pop 
			R = Pop();
			if ( pushpop == 1 ) {	// 叶节点 
				T[R].Left = Null;
				T[R].Right = Null;
			} else if ( pushpop == 0 ) {
				
			}
			record = R;
			pushpop = 0;
		}
	}

	PostOrderTraversal(Root);
	if ( N ) {
		printf("%d", A[0]);
		for ( int i=1; i<N; i++ ) {
		printf(" %d", A[i]);
		}
	}
	
	return 0;
}