PAT (Advanced Level) Practice 1086 Tree Traversals Again (25 分) 凌宸1642

题目描述：

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.

译：可以使用堆栈以非递归方式实现中序二叉树遍历。 例如，假设遍历一棵6节点的二叉树（键从1到6），栈操作为：push(1)； push(2)；push(3)； pop() ; pop() ; push(4)；pop() ; pop() ; push(5)；push(6)；pop() ; pop() ;。 然后可以从这个操作序列生成一个唯一的二叉树（如图 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.

译：每个输入文件包含一个测试用例。 对于每种情况，第一行包含一个正整数 N（≤30），它是树中节点的总数（因此节点编号为 1 到 N）。 然后是 2N 行，每行描述一个堆栈操作，格式为：“Push X”，其中 X 是被压入堆栈的节点的索引； 或 "Pop" 表示从堆栈中弹出一个节点。

---

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

---

The Idea：

通过push X 的先后顺序，我们可以很自然的想到push书序就是先序遍历得到的序列，然后pop出栈的顺序就是中序遍历得到序列，有先序遍历和中序遍历，很自然的想到利用先序遍历和中序遍历重建二叉树，然后对重建的二叉树再进行后序遍历即可。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
struct node{
	int val ;
	node *l , *r ;
};
string s , s1 ;
node* root ;
int n , cnt = 0 , cnt2 = 0 , top = -1 , cnt3 = 0 ;
int pre[33] , in[33] , post[33];
node* create(int preL , int preR , int inL , int inR){
	if(preL > preR) return NULL;
	node* root = new node ;
	root->val = pre[preL] ;
	int k ; 
	for(k = inL ; k <= inR ; k ++){
		if(pre[preL] == in[k]) break ;
	}
	int numLeft = k - inL ;
	root -> l = create(preL + 1 , preL + numLeft , inL , k - 1) ;
	root -> r = create(preL + numLeft + 1 , preR , k + 1 , inR) ;
	return root ;
}
void postOrder(node *root){
	if(!root) return ;
	postOrder(root->l) ;
	postOrder(root->r) ;
	post[cnt3++] = root->val ;
}
int main(){
	cin >> n ;
	getline(cin , s) ; // 	吸收回车 
	stack<int> st ;
	for(int i = 0 ; i < 2 * n ; i ++){
		getline(cin , s) ;
		if(s.size() > 3){
			sscanf(s.substr(5 , s.size() - 5).c_str() , "%d" , &pre[cnt]) ; // 将字符串转为数字
			st.push(pre[cnt ++]) ;
		}else{
			in[cnt2 ++] = st.top() ;
			st.pop() ;
		}
	}
	root = create( 0 , n - 1 , 0 , n - 1) ;
	postOrder(root) ;
	for(int i = 0 ; i < n ; i ++)
		printf("%d%c" , post[i] , ((i == n -1)?'\n':' ')) ;
    return 0;
}