题意：根据进栈和出栈的操作可以得到一个二叉树的中序遍历，然后输出后序遍历
思路：可以看出每个进栈的顺序就是先序遍历的顺序，而出栈的顺序就是一个中序遍历的结果，故此题就是根根据先序和中序找后序的过程。此题我参考了柳神的代码用pre和in保存值得索引，而我自己做的是直接保存的值，两种方法都能AC
自己的代码：
#include<iostream> #include<vector> #include<stack> #include<string> using namespace std; vector<int> pre, in,post; stack<int> s; int n = 0, num = 0, tem = 0,key = 0; void postTravel(int inL,int inR,int preRoot) {//后序遍历 if (inL > inR)return; int i = inL; while (i < n&&in[i] != pre[preRoot]) i++; postTravel(inL, i - 1, preRoot + 1); postTravel(i+1, inR, preRoot+(i-inL)+1); post.push_back(in[i]); } int main() { string str; cin >> n; for (int i = 0; i < 2 * n; i++) { cin >> str; if (str[1] == 'u') {//push进栈的顺序即为先序遍历 cin >> num; pre.push_back(num); s.push(num); } else {//出栈的顺序即为中序遍历 tem = s.top(); in.push_back(tem); s.pop(); } } postTravel(0,n-1,0); for (int i = 0; i < post.size();i++) { printf("%d%s", post[i], i == post.size() - 1 ? "\n" : " "); } system("pause"); return 0; }柳神的代码：
#include <cstdio> #include <vector> #include <stack> #include <cstring> using namespace std; vector<int> pre, in, post,value; void postorder(int root, int start, int end) { if (start > end) return; int i = start; while (i < end && in[i] != pre[root]) i++; postorder(root + 1, start, i - 1); postorder(root + 1 + i - start, i + 1, end); post.push_back(pre[root]); } int main() { int n; scanf("%d", &n); char str[5]; stack<int> s; int key=0; while (~scanf("%s", str)) { if (strlen(str) == 4) { int num; scanf("%d", &num); value.push_back(num); pre.push_back(key); s.push(key++); } else { in.push_back(s.top()); s.pop(); } } postorder(0, 0, n - 1); printf("%d", value[post[0]]); for (int i = 1; i < n; i++) printf(" %d",value[post[i]]); return 0; }核心思想都差不多，就是用pre和in保存值和索引的问题，其余小的细节可以比较
