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; }