加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

PAT 1020 Tree Traversals

发布时间:2020-12-14 04:32:07 所属栏目:大数据 来源:网络整理
导读:1020?Tree Traversals?(25?分) ? 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 correspondin
1020?Tree Traversals?(25?分)
?

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?(≤),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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node{
    int data = -1;
    node *left = NULL;
    node *right = NULL;
};
int n,cnt;

int a[31];
int b[31];

node* createtree(int start,int end){
    if(start > end)
        return NULL;
    int num = a[cnt--];
    node *t = new(node);
    t->data = num;
    if(start == end){ return t;}

    int pos = -1;
    for(int i=start;i <= end;i++){
        if(b[i] == num) pos = i;
    }

    t->right = createtree(pos+1,end);
    t->left = createtree(start,pos-1);

    return t;
}



int main(){
    cin >> n;
    cnt = n-1;

    for(int i=0;i < n;i++) cin >> a[i];
    for(int i=0;i < n;i++) cin >> b[i];

    node *root = createtree(0,n-1);

    queue<node*> que;
    que.push(root);
    int count = 0;

    while(!que.empty()){
        node *t = que.front();que.pop();
        cout << t->data;
        if(count!=n-1){cout << " ";count++;}
        if(t->left)que.push(t->left);
        if(t->right)que.push(t->right);
    }



    return 0;
}
创建节点要new,不然就会出错

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读