7-3 玩转二叉树

分数 25

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

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

输入格式：

输入第一行给出一个正整数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<iostream>
#include<vector>
#include<queue>

using namespace std;

struct node {
    int data;
    node* lchild;
    node* rchild;
};
queue<node*> que;
struct tree{
    node* root;
};

tree t;

int n;

int zhong[110];
int qian[110];
int node[110];
int note2[110];

vector<int> result;

void insert(int begin,int end,struct node* & order,int t1,int t2)
{
    if(begin>=end)
    {
        return;
    }
    struct node* temp = (struct node*)malloc(sizeof(node));
    temp->data = qian[begin];
    temp->lchild=temp->rchild=NULL;
    if(order ==t.root)
    {
        t.root =temp;
    }else{
        order = temp;
    }
    int middle = qian[begin];
    int pos = node[middle];
    insert(begin +1,pos-t1+1+begin,temp->lchild,t1,pos);
    insert(pos - t1 +1+begin,end,temp->rchild,pos+1,t2);
}

void show()
{
    struct node* temp=t.root;

    que.push(temp);
    while(!que.empty())
    {
        temp=que.front();
        result.push_back(temp->data);
        que.pop();

        //要反转二叉树，先输出右子树即可
        if(temp->rchild!=NULL)
            que.push(temp->rchild);
        if (temp->lchild!=NULL)
            que.push(temp->lchild);
    }
}
int main()
{
    cin>>n;
    int temp1;
    for(int i=0;i<n;i++){
        cin>>temp1;zhong[i]=temp1;node[temp1]=i;
    }
    for(int i=0;i<n;i++){
        cin>>temp1;qian[i]=temp1;
    }
    t.root =NULL;
    insert(0,n,t.root,0,n);
    show();
    for(int i=0;i<result.size()-1;i++)
        cout<<result[i]<<" ";
    cout << result[result.size() - 1];
    return 0;
}