PTA玩转二叉树

悠悠 2022-02-28 00:00 181阅读 0赞

*  [编程题90][90]

7-26 玩转二叉树 （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<bits/stdc++.h>
    using namespace std;
    struct Node{ int l;int r;}a[1000];
    int pre[1000],mid[1000],n;
    int build(int ml,int mr,int pl,int pr){
    	if(ml>mr)return 0;//如果不正常返回0，也就是叶节点的下一个结点	
    	int root=pre[pl],p1,num,index=ml;
    	while(mid[index]!=pre[pl])index++;
    	num=index-ml;
    	a[root].l=build(ml,index-1,pl+1,pl+num);
    	a[root].r=build(index+1,mr,pl+num+1,pr);
    	return root;
    }
    void bfs(int root){
    	queue<int> ans;
    	vector<int> res;
    	ans.push(root);
    	while(!ans.empty()){
    		int t=ans.front();ans.pop();	
    		if(t==0)break;//发生了错误 
    		res.push_back(t); 
    		if(a[t].r!=0)ans.push(a[t].r);
    		if(a[t].l!=0)ans.push(a[t].l);
    	}
    	cout<<res[0];
    	for(int i=1;i<res.size();i++)cout<<" "<<res[i];
    }
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++)cin>>mid[i];
    	for(int i=1;i<=n;i++)cin>>pre[i];
    	int root=build(1,n,1,n);
    	bfs(root);	
    	return 0;
    }

[90]: https://pintia.cn/problem-sets/1103248431881637888/problems/type/7

发表评论取消回复

表情：

评论列表（有 0 条评论，181人围观）

还没有评论，来说两句吧...

相关阅读

相关【二叉树】玩转二叉树

[题目详情 - L2-011 玩转二叉树 (pintia.cn)][- L2-011 _ _pintia.cn] 题意： ![dd74fbe51484428a93a3dae

左手的ㄟ右手/ 2024年03月23日 15:03/ 0 赞/ 36 阅读

相关 TypeScript 玩转二叉树

认识二叉树普通树与二叉树的区别首先把普通树与二叉树（Binary Tree）区别开来。普通树能直观地反映树状结构的数据以及它们之间的关系，和我们普通认知的树那样

悠悠/ 2023年01月15日 09:28/ 0 赞/ 139 阅读

相关 PTA-10/7 二叉树

1-4 若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为…A…B…，而中序遍历序列为…B…A…。前序和中序指的是根的访问次序，因为a和b都是叶子节点，

偏执的太偏执、/ 2022年12月12日 15:07/ 0 赞/ 91 阅读

相关 L2-011. 玩转二叉树

PAT乙级的一道题目，题目描述：给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这

刺骨的言语ヽ痛彻心扉/ 2022年09月27日 06:20/ 0 赞/ 23 阅读

相关 L2-011. 玩转二叉树

L2-011. 玩转二叉树时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard

谁践踏了优雅/ 2022年05月30日 03:44/ 0 赞/ 117 阅读

相关 L2-011. 玩转二叉树

L2-011. 玩转二叉树时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者陈越给

以你之姓@/ 2022年05月29日 02:05/ 0 赞/ 138 阅读

相关 PTA玩转二叉树

[编程题90][90] 7-26 玩转二叉树（25 分) 给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是

悠悠/ 2022年02月28日 00:00/ 0 赞/ 182 阅读

相关还原二叉树PTA

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。输入格式: 输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均

男娘i/ 2022年02月04日 13:43/ 0 赞/ 218 阅读

相关求二叉树高度PTA

本题要求给定二叉树的高度。函数接口定义： int GetHeight( BinTree BT ); 其中BinTree结构定义如下： typede

待我称王封你为后i/ 2022年02月04日 04:19/ 0 赞/ 321 阅读

相关是否二叉搜索树PTA

本题要求实现函数，判断给定二叉树是否二叉搜索树。函数接口定义： bool IsBST ( BinTree T ); 其中BinTree结构定义如下：

雨点打透心脏的1/2处/ 2022年02月03日 07:06/ 0 赞/ 220 阅读