Tree Traversals Again
一个中序遍历的非递归实现可以使用栈。 例如，假设对一棵 6 个节点（键值编号 1 到 6）的二叉树进行中序遍历，其栈操作序列为： push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop()。 则可以由此操作序列唯一地构造出一棵二叉树（见图1）。你的任务是输出该树的后序遍历序列。
Figure 1
输入格式:
每个输入文件包含一个测试用例。第一行包含一个正整数 NN（≤30≤30），表示树的节点总数（节点编号为 1 到 NN）。接下来 2N2N 行，每行描述一次栈操作，格式为：
Push X或
Pop其中Push X表示将编号为 X 的节点压入栈顶，Pop表示弹出栈顶节点。
输出格式:
对于每个测试用例，输出对应二叉树的后序遍历序列，所有数字用一个空格分隔，行末不得有多余空格。题目保证解一定存在。
样例输入:
6 Push 1 Push 2 Push 3 Pop Pop Push 4 Pop Pop Push 5 Push 6 Pop Pop样例输出:
3 4 2 6 5 1#include <iostream> #include <bits/stdc++.h> using namespace std; vector<int> zhong, qian; vector<int> ans; struct Node{ int val; Node *l; Node *r; }; Node* create(int v){ Node *p=new Node; p->val=v; p->l=p->r=NULL; return p; } Node* build(int ql,int qr,int zl,int zr,vector<int> qian,vector<int> zhong){ if(ql>qr)return 0; int root=qian[ql]; Node* t=create(root); int k=0; for(k=zl;k<=zr;++k){ if(zhong[k]==root)break; } int len=k-zl; t->l=build(ql+1,ql+len,zl,k-1,qian,zhong); t->r=build(ql+len+1,qr,k+1,zr,qian,zhong); return t; } void pri(Node* root) { if (!root) return; pri(root->l); pri(root->r); ans.push_back(root->val); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n;cin>>n;cin.ignore(); stack<int> st; for(int i=0;i<2*n;++i){ string s;getline(cin,s); if(s.find("Push")!=string::npos){ int k=stoi(s.substr(5)); qian.push_back(k); st.push(k); }else{ zhong.push_back(st.top()); st.pop(); } } Node* root=build(0,n-1,0,n-1,qian,zhong); pri(root); for(int i=0;i<ans.size();i++){ if(i>0) cout<<" "; cout<<ans[i]; } return 0; }