vlambda博客
学习文章列表

来源

https://pintia.cn/problem-sets/994805046380707840/problems/994805065406070784

题目

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

输入格式：

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

输出格式：

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

限制

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

编译器

C ++(g++)

代码

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<iostream>

using namespace std;

#define SIZE 100

typedef struct BinaryTree

{

    struct  BinaryTree* left, * right;

    int  data;

}BinTreeNode;

typedef struct queue

{

    int  rear;

    int  front;

    struct  BinaryTree* queues[SIZE];

}Queue;

BinTreeNode* CreateTree(BinTreeNode*  tree, int* PreOrder, int* InOrder, int length)

{

    int  k = 0;

    if  (length == 0) return NULL;

    while  (PreOrder[0] != InOrder[k])  k++;

    if  ((tree = (BinTreeNode*)malloc(sizeof(BinTreeNode))) == NULL)

    {

        cout << "未分配内存" << endl;

        exit(1);

    }

    tree->data  = InOrder[k];

    tree->left  = CreateTree(tree->left, PreOrder + 1, InOrder, k);

    tree->right  = CreateTree(tree->right, PreOrder + k + 1, InOrder + k + 1, length - k -  1);

    return  tree;

}

Queue* InitQueue(Queue* p)

{

    if  ((p = (Queue*)malloc(sizeof(Queue))) == NULL)

    {

        cout << "分配内存失败" << endl;

        exit(1);

    }

    p->rear  = 0;

    p->front  = 0;

    return  p;

}

void InQueue(Queue* p, BinTreeNode*  tree)

{

    if  (p->rear == SIZE) cout << "队列已满"  << endl;

    else  p->queues[p->rear++] = tree;

}

BinTreeNode* OutQueue(Queue* p)

{

    if  (p->front == p->rear) cout << "队列以空" << endl;

    else  return p->queues[p->front++];

}

void LevelOrder(BinTreeNode* tree,  Queue* p)

{

    BinTreeNode*  pr;

    InQueue(p,  tree);

    while  (p->front != p->rear)

    {

        pr = OutQueue(p);

        //cout<<pr->data;

        if (pr->left) InQueue(p, pr->left);

        if (pr->right) InQueue(p,  pr->right);

    }

}

void MirrorBinTree(BinTreeNode* tree)

{

    BinTreeNode*  temp;

    if  (tree)

    {

        temp = tree->left;

        tree->left = tree->right;

        tree->right = temp;

        MirrorBinTree(tree->left);

        MirrorBinTree(tree->right);

    }

}

int main()

{

    int  PreOrder[100];

    int  InOrder[100];

    int  length;

    Queue*  p=NULL;

    BinTreeNode*  tree=NULL;

    p  = InitQueue(p);

    cin  >> length;

    for  (int i = 0; i < length; i++) cin >> InOrder[i];

    for  (int i = 0; i < length; i++)  cin  >> PreOrder[i];

    //cin>>InOrder;//中序

    //cin>>PreOrder;//先序        

    tree  = CreateTree(tree, PreOrder, InOrder, length);

    MirrorBinTree(tree);

    LevelOrder(tree,  p);

    for  (int i = 0; i < p->rear; i++)

    {

        cout << p->queues[i]->data;

        if (i < (p->rear - 1)) cout <<  " ";

    }

    return  0;

}

解题

报告

这道题需要我们知道中序和先序去还原二叉树，

首先 我们需要知道 1先序 和中序 2后序和中序 是可以还原二叉树的

其次 层次遍历 和广度 优先搜索差不多

坑点

心得

要熟悉二叉树的知识点