PAT 甲级1086 Tree Traversals Again (25) 前序中序求后序树的遍历

/*PAT 甲级1086*/
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
vector<int> pre, in, post;
/*
1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。
*/
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;
    stack<int> s;
    char str[5];
    scanf("%d", &n);
    for(int i = 0; i < n*2; i++){
        scanf("%s", str);
        if(strlen(str) == 4){
            int n;
            scanf("%d", &n);
            s.push(n);
            pre.push_back(n);

        }
        else{
            in.push_back(s.top());
            s.pop();
        }
    }
  postorder(0, 0, n - 1);
  printf("%d", post[0]);
  for(int i = 1; i < n; i++)
        printf(" %d", post[i]);
  return 0;
}