您现在的位置是:首页 > 正文

PAT A1043 Is It a Binary Search Tree(25 分)

2024-04-01 01:32:51阅读 4

 

1043 Is It a Binary Search Tree(25 分)

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees.

If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.

Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in a line YES if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or NO if not. Then if the answer is YES, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

7
8 6 5 7 10 8 11

Sample Output 1:

YES
5 7 6 8 11 10 8

Sample Input 2:

7
8 10 11 8 6 7 5

Sample Output 2:

YES
11 8 10 7 5 6 8

Sample Input 3:

7
8 6 8 5 10 9 11

Sample Output 3:

NO
#include<cstdio>
#include<vector>
using namespace std;

const int MAXV = 1010;
int n;
int count = 0;
struct Node{
	int data;
	Node* lchild;
	Node* rchild;
};
int a[MAXV];
vector<int> preList;

void insertBST(Node* &root, int x){
	if(root == NULL){
		root = new Node;
		root->data = x;
		root->lchild = root->rchild = NULL;
		return;
	}
	if(x < root->data) insertBST(root->lchild, x);
	else insertBST(root->rchild, x);
}

void insertMirr(Node* &root, int x){
	if(root == NULL) {
		root = new Node;
		root->data = x;
		root->lchild = root->rchild = NULL;
		return;
	}
	if(x < root->data) insertMirr(root->rchild, x);
	else insertMirr(root->lchild, x);
}

Node* createBST(int a[]){
	Node* root = NULL;
	for(int i = 0; i < n; i++){
		insertBST(root, a[i]);
	}
	return root;
}

Node* createMirr(int a[]){
	Node* root = NULL;
	for(int i = 0; i < n; i++){
		insertMirr(root, a[i]);
	}
	return root;
}

void preOrder(Node* root){
	if(root == NULL) return;
	preList.push_back(root->data);
	preOrder(root->lchild);
	preOrder(root->rchild);
}

bool cmp(int inp[], vector<int> pre){
	for(int i = 0; i < n; i++){
		if(inp[i] != pre[i]) return false;
	}
	return true;
}

void postOrder(Node* node){
	if(node == NULL) return;
	postOrder(node->lchild);
	postOrder(node->rchild);
	printf("%d", node->data);
	count++;
	if(count != n) printf(" ");
	else printf("\n");
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", a + i);
	}
	Node* BST = createBST(a);
	preOrder(BST);			//获得先序遍历preList
	if(cmp(a, preList) == true){
		printf("YES\n");
		postOrder(BST);
		return 0;
	}
	Node* Mirr = createMirr(a);
	preList.clear();
	preOrder(Mirr);
	if(cmp(a, preList) == true){
		printf("YES\n");
		postOrder(Mirr);
	}else printf("NO\n");
	return 0;
}

 

网站文章

  • 怎样分析服务器的内存溢出文件,线上系统内存溢出分析方法

    怎样分析服务器的内存溢出文件,线上系统内存溢出分析方法

    点击上方蓝字关注我们一、生产环境操作系统:CentOS6.7JDK版本:jdk1.6.0_45中间件版本:apache-tomcat-6.0.37JVM堆内存配置:-Xms8192m-Xmx8192m...

    2024-04-01 01:32:25
  • 5月份华为认证考试,100%通过率!最高分九百多!

    5月份华为认证考试,100%通过率!最高分九百多!

    考试是最能测试出一个人最近一段时间的学习状态和对知识的掌握度。不然也不会有十年磨一剑只为高考这个道理了。自从西宇教育获得Pearson VUE国际认证考试中心的授权开通了PVUE考试中心。每天来考试的...

    2024-04-01 01:32:17
  • Javascript滚动条翻页数据动态加载

    Javascript Ajax滚动条翻页数据动态加载

    2024-04-01 01:32:13
  • SpringSecurity-权限校验就是这么简单(1)-如何初始化及加载多个Filter

    可能之前会省略很多,我们先了解总的概念实现,无须从头看到尾去解决某个问题了(1)SpringSecurity针对某个请求会有不同的SecurityFilterChain,而里面会有好多过滤器;也就是说我们会针对不同的请求来设置添加不同的过滤器,此场景主要用于分类、分路径请求的情况。(2)就是说说如何往SecurityFilterChain中加入不同的Filter,及加入的过程方式、注意事项...

    2024-04-01 01:32:07
  • uboot 源码官方下载地址

    uboot 源码官方下载地址

    分类: 嵌入式     U-BOOT 移植过程详解:添加一块新板子的支持http://blog.csdn.net/linuxarmsummary/article/details/44836229  最近打算开始学习uboot,得好好加油。   U-Boot,全称 Universal Boot Loader,是遵循GPL条款的开放源码项目。从FADSROM、...

    2024-04-01 01:31:41
  • 2023 Chatgpt AI绘图小说推文项目

    2023 Chatgpt AI绘图小说推文项目

    打开最强大的AI绘画工具midjourney,它能根据你提供的描述,生成任何画面。现在,我们将根据小说中描述的场景、人物和元素,告诉GPT需要生成的描述词,然后将其翻译成英文。复制这个描述,并在mid...

    2024-04-01 01:31:30
  • 基础-JAVA集合类型主要区别

    1、List,Set,Map三者的区别 List 储存一组不唯一的,有序的对象 Set 不允许重复 Map 使用键值对存储 key不能重复 2、ArrayList和LinkedList的区别 相同之处...

    2024-04-01 01:31:05
  • MySQL之事务

    MySQL之事务

    2024-04-01 01:30:58
  • 如何在 Mac 上映射网络驱动器

    如何在 Mac 上映射网络驱动器

    映射网络驱动器的最快方法是使用Finder应用程序。此方法将创建到您的网络驱动器的临时连接。但是,在您重新启动 Mac 后,它不会保留在原位。macOS 支持Samba (SMB) 网络共享。这是在 ...

    2024-04-01 01:30:51
  • 2020年华中科技大学计算机学院,2020年华中科技大学计算机应用技术考研经验分享...

    该楼层疑似违规已被系统折叠隐藏此楼查看此楼一、专业目录(101)思想政治理论(201)英语一(301)数学一(408)计算机学科专业基础综合二、参考书1. 《数据结构(C语言版)》严蔚敏 清华大学出版...

    2024-04-01 01:30:25