1086 Tree Traversals Again

题目大意

用栈的操作唯一对应一棵二叉树的中序遍历，让你输出这棵树的后序遍历。

---

思路解析

观察不难发现，每一对push和pop中间夹的节点就是栈顶这个节点的左子树，这么说可能有些难理解，我们把题目给的输入示例中pop出来的元素标注出来：

Push 1
Push 2
Push 3
Pop  3
Pop  2
Push 4
Pop  4
Pop  1
Push 5
Push 6
Pop  6
Pop  5

比如push 1和pop 1之间夹的2 3都是1的左子树，同理，3是2的左子树，6是5的左子树。
下面找右子树：每一个pop之后跟着的push都是栈顶元素的右子树。
比如pop 2之后紧跟着push 4，则4就是2的右子树，pop 1之后紧跟着push 5，则5就是1的右子树。用一个标志flag告诉程序当前是插入左子树还是右子树。
循环这个步骤就可以建立出一棵二叉树。

---

示例代码

#include<iostream>
#include<string>
#include<stack>
using namespace std;
struct node{
	int val;
	struct node* left, *right, *father;
};
node* tree = NULL;//指向根节点的指针
void post(node* n) {
	if (n == NULL) return;
	post(n->left);
	post(n->right);
	n == tree ? cout << n->val: cout << n->val << " ";
}
int main() {
	int n;
	cin >> n;
	node* pre = NULL;
	stack<node*> sta;
	bool flag = false;
	for (int i = 0; i < 2 * n; i++) {
		node* nod = new node();
		string str;
		int val;
		cin >> str;
		if (str[1] == 'u') {//push
			cin >> val;
			nod->val = val;
			if (flag) {//插入右子树
				pre->right = nod;
				flag = false;
			}
			else {//插入左子树
				i == 0 ? tree = nod : sta.top()->left = nod;
			}
			sta.push(nod);
		}
		else {//pop
			pre = sta.top();
			sta.pop();
			flag = true;
		}
	}
	post(tree);
	return 0;
}