# 11518: 【原1518】后序遍历

### 题目描述

author: 林泽冰 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1518

## Description

You are given the pre-order sequence and the in-order sequence of a binary tree.

You are required to output the post-order sequence of the tree.

(This is the problem C for SEIEE-Yu Yong Data Structure 2015 Fall Exam 1)

## Input Format

The first row is a number N which denotes the number of elements of pre-order sequence & in-order sequence. * There is no duplicate elements.

The second row is the pre-order sequence; elements are separated by a blank.

The third row is the in-order sequence; elements are separated by a blank.

## Output Format

One line, the corresponding post-order sequence.

## Sample Input

``````3
-23432134 90687980 1
90687980 -23432134 1
``````

## Sample Output

``````90687980 1 -23432134
``````

## Limits

• 20% N < 10
• 40% N < 1000
• 100% N < 100000 ; -2^31< elements < 2^31

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

class node {
public:
int val = 0;
node* lchild = nullptr,
* rchild = nullptr;
};
int pre = { 0 }, in = { 0 };

void create_tree(int pre_pos, int in_pos, int len, node* pos) {
//写入
pos->val = pre[pre_pos];
int mid;
for (mid = in_pos; in[mid] != pre[pre_pos]; ++mid);
int llen = mid - in_pos, rlen = in_pos + len - mid - 1;
if (llen) {
pos->lchild = new node;
create_tree(pre_pos + 1, in_pos, llen, pos->lchild);
}
if (rlen) {
pos->rchild = new node;
create_tree(pre_pos + 1 + llen, mid + 1, rlen, pos->rchild);
}
}

//后续遍历
void post_order(node* pos){
if (pos) {
post_order(pos->lchild);
post_order(pos->rchild);
printf("%d ", pos->val);
}
}

int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &pre[i]);
for (int i = 0; i < n; ++i)
scanf("%d", &in[i]);

node* root = new node;
create_tree(0, 0, n, root);
post_order(root);

return 0;
}
``````