PTA 天梯赛练习 7-11 玩转二叉树-二叉树重建

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

以前就思考过这个问题，但是没有深入的想过，这是一种叫二叉树重建的典型题目

如果给出中序和前序，求出后序遍历。

这道题则求的是交换儿子节点的层序遍历。

二叉树的重建应该怎么重建，首先我们知道，先根遍历，最开始的那个一定是根节点，那么，我们可以从先根遍历开始，对于先根遍历的某个节点，寻找他在中根遍历中的位置，这个位置到先根遍历的位置，中间的节点一定是其左儿子节点，而中间节点后面，一定是右儿子节点。、

#include<iostream>

#include<string.h>

#include<algorithm>

#include<stdio.h>

#include<queue>

using namespace std;

const int maxx = ;

int pre[maxx];

int in[maxx];

int pos;

struct node{

  int w,l,r;

}tree[maxx];

void build(int l,int r,int n)

{

    if (l==r){

        tree[n].w=-;//当前节点为空

        return;

    }

    int root=pre[pos++];

    tree[n].w=root;//当前节点存储的值

    tree[n].l=*n;//这个节点的左儿子节点编号

    tree[n].r=*n+;//这个节点的右儿子节点编号

    int mid=find(in+,in+r,root)-in;// 得到当前节点在中序遍历数组中的下标

    build(l,mid,*n);//重建左子树

    build(mid+,r,*n+);//重建右子树

}

void print(){

  queue<int>q;

  q.push();

  int s;

  while(!q.empty()){

    s=q.front();

    q.pop();

    if (tree[s].w!=-){

        if (s!=){

            printf(" ");

        }

        printf("%d",tree[s].w);

        q.push(tree[s].r);

        q.push(tree[s].l);

    }

  }

  printf("\n");

}

int main(){

  int n;

  while(~scanf("%d",&n)){

    pos=;

    for (int i=;i<=n;i++){

        scanf("%d",&in[i]);

    }

    for (int i=;i<=n;i++){

        scanf("%d",&pre[i]);

    }

    build(,n+,);

    print();

  }

  return ;

}