1, Title

Given the post order traversal and middle order traversal of a binary tree, please output the sequence of its sequence traversal. It is assumed that the key values are positive integers that are not equal to each other.

Input format:

The first line of input gives a positive integer N (≤ 30), which is the number of nodes in the binary tree. The second line gives the sequence of subsequent traversal. The third line gives the middle order traversal sequence. Numbers are separated by spaces.

Output format:

Output the sequence of sequence traversal of the tree in one line. The numbers shall be separated by one space, and there shall be no extra space at the beginning and end of the line.

Input sample:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Output example:

4 1 6 3 5 7 2

2, Method 1

1. Train of thought

(1) Restore binary tree

① Train of thought

Take this topic as an example:
The post order traversal is: 2 3 1 5 7 6 4; The middle order traversal is: 1 2 3 4 5 6 7

1. First of all, we need to understand: for post order traversal, its root node is at the tail; For middle order traversal, its root node is located in the middle;
2. According to this law, first find the root node "4" from the post order traversal, and then observe the mid order traversal. Taking "4" as the dividing point, the binary tree sequence is divided into two parts, in which "1,23" is the left subtree and "5,67" is the right subtree, so as to find the first layer;
3. Continue to repeat the above operations. Take the left subtree as an example. The subsequent sequence traversal is "23 1", the middle sequence traversal is "1 23", and its root node is "1". Observe the middle sequence traversal. Take "1" as the dividing point and divide it into two parts. Among them, "23" is the right subtree without left subtree;

② Code

// Given the post order and middle order, find the binary tree
LPNODE insert(int root, int start,int end)
{
    LPNODE tree;
    if (start > end) return NULL;
    int i;
    for (i = start; a[root] != b[i]; i++);
    tree = (LPNODE)malloc(sizeof(NODE));
    tree->data = a[root];
    tree->left = insert(root - (end - i) - 1, start, i - 1);
    tree->right = insert(root - 1, i + 1, end);
    return tree;
}

(2) Binary tree sequence traversal

① Train of thought

The sequence traversal of binary tree is usually completed with the help of queue. This problem can be completed with its practical array:

1. Judge whether the tree is empty;
2. Mark the root node and judge whether the root node has left subtree and right subtree. If so, put its nodes into the array;
3. Cycle output is enough;

Key points: two marking points: start and end. Each cycle of start must be + +, end. When the current node has a subtree + +, when start == end, it means that the tree has been traversed and the cycle ends;

② Code

// level traversal 
void LayerOrder(LPNODE tree)
{
    if (tree == NULL)
        return;
    int flag = 0;
    LPNODE queue[max];
    int start = -1; int end = 0;
    queue[end] = tree;
    while (start != end) {
        start++;//Ensure that there are no spaces before the first number of outputs
        if (flag)
            printf(" ");
        printf("%d", queue[start]->data);
        flag++;
        if (queue[start]->left != NULL) {
            end++;
            queue[end] = queue[start]->left;
        }
        if (queue[start]->right != NULL) {
            end++;
            queue[end] = queue[start]->right;
        }
    }
}

2. Code

#include<stdio.h>
#include<stdlib.h>
#define max 50

// Defines the node structure of a binary tree
typedef struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;
}NODE, * LPNODE;

LPNODE insert(int root, int start, int end); // Creation of mirrored binary tree
void LayerOrder(LPNODE tree); // level traversal 

int n;
int i, j; // count
LPNODE Tree = NULL; // Binary tree
int a[max], b[max]; // A - > post order B - > middle order

int main()
{
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (i = 0; i < n; i++)
    {
        scanf("%d", &b[i]);
    }
    Tree = insert(n - 1, 0, n - 1);
    LayerOrder(Tree);
    return 0;
}

// Given the post order and middle order, find the binary tree
LPNODE insert(int root, int start,int end)
{
    LPNODE tree;
    if (start > end) return NULL;
    int i;
    for (i = start; a[root] != b[i]; i++);
    tree = (LPNODE)malloc(sizeof(NODE));
    tree->data = a[root];
    tree->left = insert(root - (end - i) - 1, start, i - 1);
    tree->right = insert(root - 1, i + 1, end);
    return tree;
}

// level traversal 
void LayerOrder(LPNODE tree)
{
    if (tree == NULL)
        return;
    int flag = 0;
    LPNODE queue[max];
    int start = -1; int end = 0;
    queue[end] = tree;
    while (start != end) {
        start++;//Ensure that there are no spaces before the first number of outputs
        if (flag)
            printf(" ");
        printf("%d", queue[start]->data);
        flag++;
        if (queue[start]->left != NULL) {
            end++;
            queue[end] = queue[start]->left;
        }
        if (queue[start]->right != NULL) {
            end++;
            queue[end] = queue[start]->right;
        }
    }
}