给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

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

输出样例：

4 6 1 7 5 3 2


#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
struct ydw{
    int data;
    struct ydw *l,*r;
};
int pre[101],in[101],n;
ydw *creat(int zl,int zr,int ql,int qr)//中序左右，前序左右孩子 
{
    if(ql>qr||zl>zr)return NULL;
    ydw *root=new ydw;
    int k=0,i;
    root->data=pre[ql];
    while(in[zl+k]!=root->data)k++;
    root->l=creat(zl,zl+k-1,ql+1,ql+k);//这好像也挺好推的 
    root->r=creat(k+1+zl,zr,ql+k+1,qr);
    return root;
} 
void bfs(ydw *root)
{
    queue<ydw*>qu;
    qu.push(root);
    int l=0;
    while(!qu.empty())
    {
        ydw *t=qu.front();
        qu.pop();
        l++;
        printf("%d%c",t->data,l==n?'\n':' ');
        if(t->r!=NULL)qu.push(t->r);//镜像输出 
        if(t->l!=NULL)qu.push(t->l);
    }
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&in[i]);
    for(i=0;i<n;i++)
        scanf("%d",&pre[i]);
    ydw *root=creat(0,n-1,0,n-1);
    bfs(root);
    return 0;
}

View Code

 

版权声明：本文为ydw--原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/ydw--/p/10569543.html