L2-011. 玩转二叉树
时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越
给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数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<bits/stdc++.h>
using namespace std;
typedef struct node
{
int data;
struct node*l;
struct node*r;
}tree;
tree* creat1(int xian[],int zhong[] ,int len)
{
if(len<=0)
return NULL;
tree*head = new tree;
head->data = *xian;
int i = 0;
for(;i<len;i++)
{
if(zhong[i]==*xian)
{
break;
}
}
head->l = creat1(xian+1,zhong,i);
head->r = creat1(xian+i+1,zhong+i+1,len-i-1);
return head;
}
void cccout(tree*root)
{
tree*p = NULL;
queue<tree*>g;
if(root)
{
g.push(root);
}
while(!g.empty())
{
p = g.front();
g.pop();
cout<<p->data<<" ";
if(p->l)
{
g.push(p->l);
}
if(p->r)
{
g.push(p->r);
}
}
}
void xxian(tree*root)
{
if(root)
{
cout<<root->data<<" ";
xxian(root->l);
xxian(root->r);
}
}
void ccout(tree*root)
{
queue<tree*>q;
tree*p =NULL;
if(root)
{
q.push(root);
}
int top = 1;
while(!q.empty())
{
p = q.front();
q.pop();
if(top)top =0;
else printf(" ");
cout<<p->data;
if(p->l)
{
q.push(p->l);
}
if(p->r)
{
q.push(p->r);
}
}
}
void swap(tree*root)
{
if(!root) return ;
swap(root->l);
swap(root->r);
swap(root->l,root->r);
}//或者在层序遍历的时候倒过来
int main()
{
int n;
cin>>n;
int xian[36],zhong[36];
for(int i=0;i<n;i++)
{
cin>>zhong[i];
}
for(int i=0;i<n;i++)
{
cin>>xian[i];
}
tree*root = new tree;
root = creat1(xian,zhong,n);
swap(root);
ccout(root);
return 0;
}
静态数组版
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=1000000;
int n,num(0);
int pre[maxn],in[maxn],tree[maxn];
void build(int tag,int left,int right)
{
tree[tag]=pre[++num];
if(left==right)
return;
int index=-1;
for(int i=left;i<=right;i++)
{
if(in[i]==tree[tag])
{
index=i;
break;
}
}
if(index==-1)
return;
if(index-1>=left)
build(tag<<1,left,index-1);
if(index+1<=right)
build(tag<<1|1,index+1,right);
}
void bfs()
{
queue<int> que;
que.push(1);
int tag=tree[1];
while(!que.empty())
{
int temp=que.front();
que.pop();
if(tree[temp]!=tag)
printf(" ");
printf("%d",tree[temp]);
if(tree[temp*2+1]!=0)
que.push(temp*2+1);
if(tree[temp*2]!=0)
que.push(temp*2);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&in[i]);
for(int i=1;i<=n;i++)
scanf("%d",&pre[i]);
build(1,1,n);
bfs();
printf("\n");
return 0;
}