1020. Tree Traversals (25)

深碍√TFBOYSˉ_ 2022-05-31 08:36 186阅读 0赞

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:**

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

**Sample Output:**

4 1 6 3 5 7 2

--------------------

题目大意：

假设二叉树中所有的键值都是不同的正整数。给出后序遍历和中序遍历序列，你的任务是输出相应的层次遍历序列。  
输入规格：  
每个输入文件包含一个测试用例。对于每个测试用例，第一行给出一个正整数N（<=30）,即二叉树中的节点总数。第二行给出后序遍历序列，第三行给出中序遍历序列。直线上得所有数字都用空格隔开。  
输出规范：  
对于那个测试用例，在一行中打印出相应的层次遍历序列。直线上得所有数字用一个空格隔开，在这一行的末尾没有多余的空格。

代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<queue>
    using namespace std;
    struct node
    {
        int data;
        struct node *lchild,*rchild;
    };
    struct node *create(int n,int *a,int *b)
    {
    struct node *root;
    int *p;
    if(n==0)
    return NULL;
    root=(struct node *)malloc(sizeof(struct node));
    root->data=a[n-1];
    for(p=b;p<p+n;p++)
    if(*p==a[n-1])
    break;
    int t;
    t=p-b;
    root->lchild=create(t,a,b);
    root->rchild=create(n-t-1,a+t,p+1);
    return root;
    }
    void level(struct node *T)
    {
        int i=0;
        struct node *p;
        queue<struct node *> que;
        que.push(T);
        while(!que.empty())
        {
            if(que.front())
            {
                p=que.front();
            que.push(p->lchild);
            que.push(p->rchild);
           if(i==0)
           {
               i++;
               printf("%d",p->data);
           }
           else
           {
               printf(" %d",p->data);
           }
            }
            que.pop();
        }
    }
    void cengci(struct node *root)
    {
    int out=0,in=0,i=0;
    struct node *q[100];
    q[in++]=root;
    while(in>out)
    {
    if(q[out])
    {
        if(i==0)
    {
        i++;
        printf("%d",q[out]->data);
    }
    else
       printf(" %d",q[out]->data);
    q[in++]=q[out]->lchild;
    q[in++]=q[out]->rchild;
    }
    out++;
    }
    }
    int main()
    {
        int i,j,n,m,k,t,a[31],b[31];
        struct node *root;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",&b[i]);
        }
        root=create(n,a,b);
        level(root);
        //cengci(root);
        return 0;
    }