目录
1，题目描述
题目大意
2，思路
3，AC代码
4，解题过程
第一搏
1，题目描述
implemented：使生效; 贯彻; 执行; 实施；
Sample Input:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
Sample Output:
3 4 2 6 5 1
题目大意
用栈的一些操作，模拟树的构建，并输出树的后序遍历。
2，思路
将入栈的序列，看作先序遍历；出栈的序列看作中序遍历；（根据例子中的图形得出的结论）根据树的遍历特点（先序遍历第一个节点为根节点，找到此节点在中序遍历中的位置，即可将树划分为左右两子树，具体可参考@&再见萤火虫&【PAT_甲级_1020 Tree Traversals (25分) (C++)【树的遍历】】）将根节点依次放入postOrder中（由于是将根节点逐个存入，故为了保证正确顺序，先遍历右子树，再遍历左子树，最后逆序输出）；
对函数的补充说明：
3，AC代码
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> inOrder, preOrder, postOrder;
void getPostOrder(int head, int tail, int root){
if(head > tail) return;
postOrder.push_back(preOrder[root]);
for(int i = head; i <= tail; i++){
if(inOrder[i] == preOrder[root]){
getPostOrder(i + 1, tail, root + i - head + 1);
getPostOrder(head, i - 1, root + 1);
return;
}
}
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
stack<int> sta;
string s;
cin>>N;
int num;
for(int i = 0; i < 2 * N; i++){
cin>>s;
if(s[1] == 'u'){
cin>>num;
sta.push(num);
preOrder.push_back(num);
}else{
num = sta.top();
sta.pop();
inOrder.push_back(num);
}
}
getPostOrder(0, N - 1, 0);
cout<<postOrder[N - 1];
for(int i = N - 2; i >= 0; i--)
cout<<' '<<postOrder[i];
return 0;
}
4，解题过程
第一搏
理解题意后（先序+中序=》后序），想起了上一次膜拜柳神的题目，和这个基本差不多（后序+中序=》先序=》层次遍历），传送门@&再见萤火虫&【PAT_甲级_1020 Tree Traversals (25分) (C++)【树的遍历】】
比那一题还要简单些。。。
一发入魂
