github 地址：https://github.com/iofu728/PAT-A-by-iofu728 难度：☆☆★ 关键词：二叉树遍历

# 题目

1086 Tree Traversals Again （25） An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Input Specification: Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.

Output Specification: For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

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

# 大意

给出堆栈的中序遍历过程，输出后序

# 思路

给出堆栈的中序，即给出前序+中序，求后序

# code

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

vector<int> pre, in, post;

void postorder(int root, int start, int end) {
  if (start > end) return;
  int temp = start;
  while (pre[root] != in[temp] && temp < end) ++temp;
  postorder(root + 1, start, temp - 1);
  postorder(root + temp - start + 1, temp + 1, end);
  post.push_back(pre[root]);
}

int main(int argc, char const *argv[]) {
  int n, num;
  string str;
  stack<int> s;
  cin >> n;
  while (cin >> str) {
    if (str == "Push") {
      cin >> num;
      pre.push_back(num);
      s.push(num);
    } else {
      in.push_back(s.top());
      s.pop();
    }
  }
  postorder(0, 0, n - 1);
  for (int i = 0; i < n; ++i) {
    if (i) cout << ' ';
    cout << post[i];
  }
  return 0;
}