PAT1020.Tree Traversals

题目

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

1
2
3


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

Sample Output:

1

4 1 6 3 5 7 2

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

struct node{
    int data;
    node* rchild;
    node* lchild;
};

int post[35];
int in[35];
int level[35];
node* create(int postL,int postR,int inL,int inR)
{
    if(postL>postR)
        return NULL;

    node* root=new node;
    root->data=post[postR];

    int k;
    for(int i=inL;i<=inR;i++)
        if(post[postR]==in[i])
            k=i;
    int lenl=k-inL;
    //lchild
    root->lchild=create(postL,postL+lenl-1,inL,k-1);
    //rchild
    root->rchild=create(postL+lenl,postR-1,k+1,inR);

    return root;
}

void traversal(node* root)
{
    queue<node*> Q;
    Q.push(root);
    int i=0;
    while(!Q.empty())
    {
        node* tmp;
        tmp=Q.front();
        Q.pop();
        level[i]=tmp->data;
        i++;
        if(tmp->lchild!=NULL)
            Q.push(tmp->lchild);
        if(tmp->rchild!=NULL)
            Q.push(tmp->rchild);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&post[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&in[i]);
    node* root=new  node;
    root=create(0,n-1,0,n-1);
    traversal(root);
    for(int i=0;i<n-1;i++)
        printf("%d ",level[i]);
    printf("%d",level[n-1]);


    return 0;
}

分析

二叉树的重建需要中序+{先序、后序、层序}中任意一个，后三种的目的是提供树根节点的序号，中序在获得根节点序号后可以把左子树和右子树区分开。

一次AC，开心~