A1020. Tree Traversals(25)

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

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

  1. 建树

  2. BFS

    include

    using namespace std;
    const int MAXN=35;
    int post[MAXN];
    int in[MAXN];
    int pre[MAXN];
    int n;
    struct node{

    1. int data;
    2. node* lchild;
    3. node* rchild;

    };
    node* create(int postL,int postR,int inL,int inR){

    1. if(postL>postR)return NULL;
    2. node* root=new node;
    3. root->data=post[postR];
    4. int k;
    5. for(k=inL;k<=inR;k++){
    6.     if(in[k]==post[postR])break;
    7. }
    8. int numLeft=k-inL;
    9. root->lchild=create(postL,postL+numLeft-1,inL,k-1);
    10. root->rchild=create(postL+numLeft,postR-1,k+1,inR);
    11. return root;

    }
    int num=0;
    void BFS(node* root){

    1. queue<node*>q;
    2. q.push(root);
    3. while(!q.empty()){
    4.     node* now=q.front();
    5.     q.pop();
    6.     printf("%d",now->data);
    7.     num++;
    8.     if(num<n)printf(" ");
    9.     if(now->lchild!=NULL)q.push(now->lchild);
    10.     if(now->rchild!=NULL)q.push(now->rchild);
    11. }

    }
    int main(){

    1. scanf("%d",&n);
    2. for(int i=0;i<n;i++){
    3.     scanf("%d",post+i);
    4. }
    5. for(int i=0;i<n;i++){
    6.     scanf("%d",in+i);
    7. }
    8. node* root=create(0,n-1,0,n-1);
    9. BFS(root);
    10. return 0;

    }

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

发表评论

表情：
评论列表 （有 0 条评论，306人围观）

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

相关阅读

    相关 1020. 月饼 (25)

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

    分手后的思念是犯贱分手后的思念是犯贱/ 0 赞/ 321 阅读

    相关 1020. 月饼 (25)

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

    阳光穿透心脏的1/2处阳光穿透心脏的1/2处/ 0 赞/ 288 阅读

    相关 A1020. Tree Traversals(25)

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

    桃扇骨桃扇骨/ 0 赞/ 307 阅读