A1020. Tree Traversals(25)

桃扇骨 2021-12-23 14:13 134阅读 0赞

这是一题二叉树遍历的典型题，告诉我们中序遍历和另外一种遍历序列，然后求任何一种遍历序列。  
这题的**核心**：

1.  建树
2.  BFS

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=35;
    int post[MAXN];
    int in[MAXN];
    int pre[MAXN];
    int n;
    struct node{
        int data;
        node* lchild;
        node* rchild;
    };
    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(k=inL;k<=inR;k++){
            if(in[k]==post[postR])break;
        }
        int numLeft=k-inL;
        root->lchild=create(postL,postL+numLeft-1,inL,k-1);
        root->rchild=create(postL+numLeft,postR-1,k+1,inR);
        return root;
    }
    int num=0;
    void BFS(node* root){
        queue<node*>q;
        q.push(root);
        while(!q.empty()){
            node* now=q.front();
            q.pop();
            printf("%d",now->data);
            num++;
            if(num<n)printf(" ");
            if(now->lchild!=NULL)q.push(now->lchild);
            if(now->rchild!=NULL)q.push(now->rchild);
        }
    }
    int main(){
        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=create(0,n-1,0,n-1);
        BFS(root);
        return 0;
    }

转载于:https://www.cnblogs.com/MarkKobs-blog/p/10570036.html

发表评论取消回复

表情：

评论列表（有 0 条评论，134人围观）

还没有评论，来说两句吧...

相关阅读

相关 1020. 月饼 (25)

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。注意：销

分手后的思念是犯贱/ 2022年07月15日 08:09/ 0 赞/ 144 阅读

相关 1020. Tree Traversals (25)

Suppose that all the keys in a binary tree are distinct positive integers. Given the pos

深碍√TFBOYSˉ_/ 2022年05月31日 08:36/ 0 赞/ 130 阅读

相关 1102. Invert a Binary Tree (25)

The following is from Max Howell @twitter: Google: 90% of our engineers use the softwar

拼搏现实的明天。/ 2022年05月30日 06:09/ 0 赞/ 121 阅读

相关 1086. Tree Traversals Again (25)

An inorder binary tree traversal can be implemented in a non-recursive way with a stack.

﹏ヽ暗。殇╰゛Y/ 2022年05月29日 21:11/ 0 赞/ 77 阅读

相关 1020. 月饼 (25)

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。注意：销

阳光穿透心脏的1/2处/ 2022年05月26日 04:54/ 0 赞/ 132 阅读

相关 PAT甲级 - 1020 Tree Traversals （25 分）

题目链接：[PAT甲级 - 1020 Tree Traversals （25 分）][PAT_ - 1020 Tree Traversals _25] Suppose tha

た入场券/ 2022年03月17日 01:16/ 0 赞/ 139 阅读

相关【leetcode】1028. Recover a Tree From Preorder Traversal

题目如下： > We run a preorder depth first search on the `root` of a binary tree. > > At ea

野性酷女/ 2022年01月07日 11:31/ 0 赞/ 120 阅读

相关 A1020. Tree Traversals(25)

这是一题二叉树遍历的典型题，告诉我们中序遍历和另外一种遍历序列，然后求任何一种遍历序列。这题的核心： 1. 建树 2. BFS include<bits/

桃扇骨/ 2021年12月23日 14:13/ 0 赞/ 135 阅读

相关 1020 Tree Traversals (25 分) 给出后序和中序遍历，输出层序遍历

1020 Tree Traversals (25 分) Suppose that all the keys in a binary tree are distinct pos

本是古典何须时尚/ 2021年10月30日 00:44/ 0 赞/ 154 阅读

相关 PAT A1020 Tree Traversals [二叉树后序中序求层序]

题目描述 [链接][Link 1] 给定后序和中序，求层序结果分析递归实现，这里给出先序和后序，求中序的递归：考虑中间过程

客官°小女子只卖身不卖艺/ 2021年10月23日 15:48/ 0 赞/ 197 阅读