PAT_A_1086 Tree Traversals Again

题意：根据进栈和出栈的操作可以得到一个二叉树的中序遍历，然后输出后序遍历

思路：可以看出每个进栈的顺序就是先序遍历的顺序，而出栈的顺序就是一个中序遍历的结果，故此题就是根根据先序和中序找后序的过程。此题我参考了柳神的代码用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保存值和索引的问题，其余小的细节可以比较