PAT 1174 Left-View of Binary Tree 题干不知所云

这篇具有很好参考价值的文章主要介绍了PAT 1174 Left-View of Binary Tree 题干不知所云。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人学习记录,代码难免不尽人意。

The left-view of a binary tree is a list of nodes obtained by looking at the tree from left hand side and from top down. For example, given a tree shown by the figure, its left-view is { 1, 2, 3, 4, 5 }
PAT 1174 Left-View of Binary Tree 题干不知所云,PTA,开发语言,c++,算法,pat,数据结构
Given the inorder and preorder traversal sequences of a binary tree, you are supposed to output its left-view.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20), which is the total number of nodes in the tree. Then given in the following 2 lines are the inorder and preorder traversal sequences of the tree, respectively. All the keys in the tree are distinct positive integers in the range of int.

Output Specification:
For each case, print in a line the left-view of the tree. All the numbers in a line are separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input:
8
2 3 1 5 4 7 8 6
1 2 3 6 7 4 5 8
Sample Output:
1 2 3 4 5

#include<cstdio> 
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<string> 
#include<vector>
using namespace std;
struct node{
	int data;
	node* lchild;
	node* rchild;
	int height;
};
node* newnode(int data){
	node* root=new node;
	root->data=data;
	root->lchild=NULL;
	root->rchild=NULL;
	root->height=1;
	return root;
}
int pre[25];
int in[25];
node* create(int prel,int prer,int inl,int inr){
	if(prel>prer) return NULL;
	int mid=pre[prel];
	int index;
	for(int i=inl;i<=inr;i++){
		if(in[i]==mid){
			index=i;
			break;
		}
	}
	int leftnum=index-inl;
	node* root=newnode(mid);
	root->lchild=create(prel+1,prel+leftnum,inl,index-1);
	root->rchild=create(prel+leftnum+1,prer,index+1,inr);
	return root;
}
vector<int> v;



void bfs(node* root){
	queue<node*> q;
	q.push(root);
	while(!q.empty()){
		node* now=q.front();
		q.pop();
		if(now->lchild!=NULL){
			now->lchild->height=now->height+1;
			q.push(now->lchild);
		}
		if(now->rchild!=NULL){
			now->rchild->height=now->height+1;
			q.push(now->rchild);
		}
	}
	q.push(root);
	int num=1;
	bool flag=true;
	while(!q.empty()){
			node* now=q.front();
		q.pop();
		if(now->height==num&&flag){
			v.push_back(now->data);
			flag=false;
		}
		if(now->lchild!=NULL){
			num=now->lchild->height;
			flag=true;
			q.push(now->lchild);
		}
		if(now->rchild!=NULL){
			num=now->rchild->height;
			flag=true;
			q.push(now->rchild);
		}
	}
}
int main(){
    int n;
    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]);
	} 
	node* root=create(0,n-1,0,n-1);
	bfs(root);
	for(int i=0;i<v.size();i++){
		printf("%d",v[i]);
		if(i!=v.size()-1) printf(" ");
		else printf("\n");
	}
}

强烈谴责这道题的出题人!要么出题人觉得这道题题干描述的很“清楚”了,居高临下没有站在考生的角度思考问题,要么就是故意玩文字游戏加大难度!
我们来看这道题的描述:The left-view of a binary tree is a list of nodes obtained by looking at the tree from left hand side and from top down. For example, given a tree shown by the figure, its left-view is { 1, 2, 3, 4, 5 },翻译成汉语就是二叉树的左视图是通过从左侧和从上到下查看树获得的节点列表。例如,给定如图所示的树,其左视图为{1,2,3,4,5}
问题是,例题给的树太随意了,根本让人理解不了什么是“left hand side”,我一开始以为是这样子:先遍历左子树,左子树遍历完了再从右子树低于左子树最后一个节点的左子树开始遍历!是不是很绕!后来基本只能通过几个测试点我就知道不是这样做。后来看了别人的做法才知道是输出每一行的最左侧的节点!真的是无语了,就不能在题目中直说啊,或者你多举几个普通点的树让大伙猜一猜啊,真的是。下面附上知道做法时候的代码:文章来源地址https://www.toymoban.com/news/detail-696808.html

#include<cstdio> 
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<string> 
#include<vector>
using namespace std;
struct node{
	int data;
	node* lchild;
	node* rchild;
	int height;
};
node* newnode(int data){
	node* root=new node;
	root->data=data;
	root->lchild=NULL;
	root->rchild=NULL;
	root->height=1;
	return root;
}
int pre[25];
int in[25];
node* create(int prel,int prer,int inl,int inr){
	if(prel>prer) return NULL;
	int mid=pre[prel];
	int index;
	for(int i=inl;i<=inr;i++){
		if(in[i]==mid){
			index=i;
			break;
		}
	}
	int leftnum=index-inl;
	node* root=newnode(mid);
	root->lchild=create(prel+1,prel+leftnum,inl,index-1);
	root->rchild=create(prel+leftnum+1,prer,index+1,inr);
	return root;
}
vector<int> v;



void bfs(node* root){
	queue<node*> q;
	q.push(root);
	while(!q.empty()){
		node* now=q.front();
		q.pop();
		if(now->lchild!=NULL){
			now->lchild->height=now->height+1;
			q.push(now->lchild);
		}
		if(now->rchild!=NULL){
			now->rchild->height=now->height+1;
			q.push(now->rchild);
		}
	}
	q.push(root);
	int num=1;
	bool flag=true;
	while(!q.empty()){
			node* now=q.front();
		q.pop();
		if(now->height==num&&flag){
			v.push_back(now->data);
			flag=false;
		}
		if(now->lchild!=NULL){
			num=now->lchild->height;
			flag=true;
			q.push(now->lchild);
		}
		if(now->rchild!=NULL){
			num=now->rchild->height;
			flag=true;
			q.push(now->rchild);
		}
	}
}
int main(){
    int n;
    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]);
	} 
	node* root=create(0,n-1,0,n-1);
	bfs(root);
	for(int i=0;i<v.size();i++){
		printf("%d",v[i]);
		if(i!=v.size()-1) printf(" ");
		else printf("\n");
	}
}

到了这里,关于PAT 1174 Left-View of Binary Tree 题干不知所云的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉树(binary tree)

    二叉树(Binary Tree)是一种常见的树状数据结构,它由一组节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点: 每个节点最多有两个子节点,分别称为左子节点和右子节点。 左子树和右子树也是二叉树,它们的结构与父节点类似。

    2024年02月09日
    浏览(42)
  • 平衡二叉树(Balanced Binary Tree)

    平衡二叉树是一种特殊的二叉搜索树,它具有以下特点: 每个节点的左子树和右子树的高度差不超过1。 所有的子树也都是平衡二叉树。 通过保持平衡性,平衡二叉树可以在最坏情况下仍然具有较好的性能,保证查找、插入和删除操作的时间复杂度为O(log n)。 平衡二叉树的常

    2024年02月09日
    浏览(36)
  • 数据结构与算法 | 二叉树(Binary Tree)

    二叉树(Binary Tree)是一种树形数据结构,由节点构成,每个节点最多有两个子节点:一个左子节点和一个右子节点。 \\\"二叉树\\\"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树

    2024年02月08日
    浏览(40)
  • 二叉搜索树(Binary_Search_Tree)

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值。 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值。 它的左右子树也分别为二叉搜索树。 如: a、从根开始

    2024年04月28日
    浏览(36)
  • 【C++】二叉搜索树Binary Search Tree

    二叉搜索树又被称为二叉排序树,顾名思义,当我们使用中序遍历时,会得到一个有序的序列。二叉搜索树有如下的性质: 1.若它的左子树不为空,则左子树上每个节点的值都小于根节点的值。 2.若它的右子树不为空,则右子树上每个节点的值都大于根节点的值。 3.左右子树

    2024年02月07日
    浏览(44)
  • 二叉查找树(binary search tree)(难度7)

    C++数据结构与算法实现(目录) 答案在此:二叉查找树(binary search tree)(答案) 写在前面 部分内容参《算法导论》 基本接口实现 1 删除 删除值为value的第一个节点 删除叶子节点1 删除叶子节点1 (3)删除叶子节点1 删除有两个孩子的节点z 分成下面几个步骤进行: 1 找到

    2024年02月10日
    浏览(44)
  • 二叉搜索树(Binary Search Tree,BST)

    二叉搜索树(Binary Search Tree),也称二叉查找树或二叉排序树,是一种特殊的二叉树,它满足以下性质 对于二叉搜索树的每个节点 左子树中的所有节点的值都小于该节点的值 右子树中的所有节点的值都大于(或等于)该节点的值 对于二叉搜索树的任意节点,其左子树和右子

    2024年02月09日
    浏览(44)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(44)
  • LeetCode //C - 124. Binary Tree Maximum Path Sum

    A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum

    2024年02月09日
    浏览(39)
  • 最优二叉搜索树(Optimal Binary Search Tree)_20230401

    前言 如果有序数组或有序表中的各个元素查找概率相等,那么采用二叉搜索树(BST)进行折半查找,性能最优。如果有序表中各个记录的查找概率不相等,情况又如何呢? 先看一个具体例子。已知有序表keys, 同时给出各个元素的查询频率,注意到各个元素的查询频率不相同。

    2024年02月12日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包