一个中序遍历的非递归实现可以使用栈。 例如假设对一棵 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; vectorint zhong, qian; vectorint ans; struct Node{ int val; Node *l; Node *r; }; Node* create(int v){ Node *pnew Node; p-valv; p-lp-rNULL; return p; } Node* build(int ql,int qr,int zl,int zr,vectorint qian,vectorint zhong){ if(qlqr)return 0; int rootqian[ql]; Node* tcreate(root); int k0; for(kzl;kzr;k){ if(zhong[k]root)break; } int lenk-zl; t-lbuild(ql1,qllen,zl,k-1,qian,zhong); t-rbuild(qllen1,qr,k1,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;cinn;cin.ignore(); stackint st; for(int i0;i2*n;i){ string s;getline(cin,s); if(s.find(Push)!string::npos){ int kstoi(s.substr(5)); qian.push_back(k); st.push(k); }else{ zhong.push_back(st.top()); st.pop(); } } Node* rootbuild(0,n-1,0,n-1,qian,zhong); pri(root); for(int i0;ians.size();i){ if(i0) cout ; coutans[i]; } return 0; }