postorder

题目描述
Given the pre-order traversal sequence A[] and in-order traversal sequence B[] of a tree, find the post-order traversal sequence.

输入描述
Input contains 3 lines;
The first line contains an integer n(n <= 100000), the number of node in the tree.
The second line contains n distinct intergers, which is the sequence A[](0 <= a0,a2,…,an-1<= n-1).
The third line contains n distinct intergers, which is the sequence B[](0 <= b0,b2,…,bn-1<= n-1).

输出描述
The postorder traversal sequence of the tree.

输入样例
10
7 2 0 5 8 4 9 6 3 1
7 5 8 0 4 2 6 3 9 1

输出样例
8 5 4 0 3 6 1 9 2 7

Yizuodi的答案

#include<iostream>
#include <vector>
using namespace std;

vector<int> pre;
vector<int> in;

void post(int root,int start,int ends){//后序打印
  if(start>ends){
    return;
  }
  int i=start;
  while(i<ends&&in[i]!=pre[root]){//找到中序序列中根结点的位置
    i++;
  }
  post(root+1,start,i-1);//遍历左子树
  post(root+(i-start+1),i+1,ends);//遍历右子树
  cout<<pre[root]<<' ';
}

int main(){
    int size;
    cin >> size;
    for (int i = 0; i < size; i++)
    {
        int tmp;
        cin >> tmp;
        pre.push_back(tmp);
    }
    for (int i = 0; i < size; i++)
    {
        int tmp;
        cin >> tmp;
        in.push_back(tmp);
    }
    post(0,0,size-1);
}