PAT Advanced 1043

1043. Is It a Binary Search Tree (25)

时间限制

400 ms

内存限制

32000 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

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<stdio.h>
#include<stdlib.h>
/*效率太低,有待改进*/
int isBST(int *a,int count)
{
	if(count==1 || count==0)
		return 1;
	int i,k;
	for(i=1;i<count;i++)
	{
		if(a[i]<a[0])
			continue;
		break;
	}
	k=i-1;
	for(;i<count;i++)
	{
		if(a[i]<a[0])
			return 0;
	}
	if(isBST(a+1,k)==1 && isBST(a+k+1,count-k-1)==1)
		return 1;
	return 0;
}

int isMirror(int *a,int count)
{
	if(count==1 || count==0)
		return 1;
	int i,k;
	for(i=1;i<count;i++)
	{
		if(a[i]>=a[0])
			continue;
		break;
	}
	k=i-1;
	for(;i<count;i++)
	{
		if(a[i]>=a[0])
			return 0;
	}
	if(isMirror(a+1,k)==1 && isMirror(a+k+1,count-k-1)==1)
		return 1;
	return 0;
}

void postorder(int *a,int count,int level)
{
	if(count==0)
		return ;
	if(count==1)
	{
		printf("%d",a[0]);
		if(level!=0)
			printf(" ");
		return ;
	}
	int i,k;
	for(i=1;i<count;i++)
	{
		if(a[i]<a[0])
			continue;
		break;
	}
	k=i-1;

	postorder(a+1,k,level+1);
	postorder(a+k+1,count-k-1,level+1);
	printf("%d",a[0]);
    if(level!=0)
		printf(" ");
}

void postorderMirror(int *a,int count,int level)
{
	if(count==0)
		return ;
	if(count==1)
	{
		printf("%d",a[0]);
		if(level!=0)
			printf(" ");
		return ;
	}
	int i,k;
	for(i=1;i<count;i++)
	{
		if(a[i]>=a[0])
			continue;
		break;
	}
	k=i-1;

	postorderMirror(a+1,k,level+1);
	postorderMirror(a+k+1,count-k-1,level+1);
	printf("%d",a[0]);
	if(level!=0)
		printf(" ");
}

int main()
{
	int n,i;
	scanf("%d",&n);
	int * a=(int *)malloc(n*sizeof(int));
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	if(isBST(a,n)==1)
	{
		printf("YES\n");
		postorder(a,n,0);
	}
	else if(isMirror(a,n)==1)
	{
		printf("YES\n");
		postorderMirror(a,n,0);
	}
	else
		printf("NO\n");
	free(a);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

2374
来自专栏计算机视觉与深度学习基础

Leetcode 258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the resul...

2025
来自专栏WD学习记录

牛客网 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

841
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

1481
来自专栏拂晓风起

java LinkedList ArrayList 随机访问效率 list.get(int index)

1085
来自专栏技术小黑屋

Java性能调优之容器扩容问题

在Java和Android编程中,我们经常使用类似ArrayList,HashMap等这些容器。这些容器少则存储几条,多则上千甚至更多。作为性能调优的一部分,容...

1131
来自专栏趣学算法

数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

/* 输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识,C 表示孩子结点标识,L/R...

3123
来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

2705
来自专栏数据结构与算法

Day2平衡树笔记

线段树不支持的操作:删除,插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快 比较好写 ||功能不全 rbt 红黑树 特...

3266
来自专栏小狼的世界

Aptana的破解

最近写JS比较多,常常苦恼与没有一个顺手的IDE。Editplus虽然用的熟,不过那个的效率太低而且代码看起来也很不方便,经过一个多月的试用,发现了一款好用的编...

1032

扫码关注云+社区

领取腾讯云代金券