天梯赛 L2-011 玩转二叉树(前中序确定唯一序列)

题目

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。

所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入N(<=30)，代表N个节点，

依次输入中序遍历序列和前序遍历序列，

输出镜像bfs序列

思路来源

https://blog.csdn.net/qq_28300479/article/details/51586833#commentsedit

题解

递归建树，每次维护对应的前序和中序序列

镜像bfs，只需先入右子后入左子

课内学过，然而课内的板子太冗长

还有就是开了个35的数组结果WA了，真实

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=60; 
int n;
int pre[maxn],in[maxn];
int lch[maxn],rch[maxn];
int build(int l1,int r1,int l2,int r2)//中序[l1,r1] 前序[l2,r2] 
{
	if(l1>r1)return 0;
	int rt=pre[l2],now=l1;//根 中序现处位置 
	while(in[now]!=rt)now++;
	int num=now-l1; 
	lch[rt]=build(l1,now-1,l2+1,l2+num);//个数相同 保证偏移量相同即可 
	rch[rt]=build(now+1,r1,l2+num+1,r2);//前序前半段是左子 后半段是右子 根左右 
	return rt;
}
void bfs(int rt)
{
	queue<int>q;
	q.push(rt);
	int cnt=0;
	while(!q.empty())
	{
		rt=q.front();
		q.pop();
		if(cnt)putchar(' ');//第一个前无空格 其余都有 
		printf("%d",rt);
		cnt++;
		if(rch[rt])q.push(rch[rt]);
		if(lch[rt])q.push(lch[rt]);
    }
    puts("");
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	scanf("%d",&in[i]);
	for(int i=0;i<n;++i)
	scanf("%d",&pre[i]);
	build(0,n-1,0,n-1);
	bfs(pre[0]);
	return 0;
}