[PAT解题报告] Tree Traversals Again
给定二叉树非递归中序遍历出入栈的顺序，求这个二叉树的后序遍历。
关键是还原二叉树。
没必要真正还原，我们直接转变为后序遍历序列，我们也用一个堆栈模拟。
遇到一个push操作，我们把该节点放入堆栈，然后标记该节点是个新的节点，设置标签0 （0表示新， 1表示旧）
遇到一个pop操作，是该节点左孩子访问完了退回到该节点的情形，我们并不真正pop出去，我们把堆栈顶的元素设置标签1，表示现在这个节点在中序时应该已经出栈了，我们整准备访问它的右孩子节点。前提条件是：堆栈顶部的标签不是1，
如果顶部标签是1，我们应该先pop出去。
总结一下：
原始push就push同时打上标签0，表示我们正在访问这个节点的左孩子
原始pop,先从堆栈里pop出标签为1的节点，表示这些节点已经pop出来了，同时输出，因为我们的堆栈是后序遍历的序列。再把栈顶的标签设置为1，表示我们要继续访问栈顶的右孩子。
关键是对遍历顺序的理解。
代码：
#include <cstdio>
#include <stack>
#include <cstring>
#include <string>
using namespace std;
stack<pair<int,int> > st;
char s[10];
int main() {
int n;
bool mark = false;
scanf("%d",&n);
for (n <<= 1; n; --n) {
scanf("%s",s);
if (s[1] == 'u') { //push
int x;
scanf("%d",&x);
st.push(make_pair(x,0));
}
else {
while ((!st.empty()) && (st.top().second == 1)) {
if (mark) {
putchar(' ');
}
else {
mark = true;
}
printf("%d",st.top().first);
st.pop();
}
if (!st.empty()) {
st.top().second = 1;
}
}
}
while (!st.empty()) {
if (mark) {
putchar(' ');
}
else {
mark = true;
}
printf("%d",st.top().first);
st.pop();
}
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1086
投递美团等公司10个岗位 >