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[100009] = { 0 }, in[100009] = { 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;
}