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
分析:
1.对输入的一段序列生成一棵二叉搜索树
2.判断:
a.此二叉树的先序遍历和输入的序列相等,则输出此二叉树的后序遍历序列
b.在 a 不成立的情况下,求这棵二叉树的镜像先序遍历序列,若和输入的序列相等,则输出二叉树的镜像后序遍历序列
c.以上都不成立时,输出 "NO"
C++代码如下:
#include<iostream>
#include<vector>
using namespace std;
#define maxn 1005
struct Node {
int data;
Node *lchild=NULL, *rchild=NULL;
}; void insert(Node* &root, int x) {
if (root == NULL) {
root = new Node;
root->data = x;
return;
}
if (x >= root->data) {
insert(root->rchild, x);
}
else
insert(root->lchild, x);
return;
} Node* createBST(const vector<int> v) {
Node* root=NULL; for (int i = ; i < v.size(); i++) {
insert(root, v[i]);
}
return root;
} vector<int>pre, pre_mirr, post,post_mirr;
void preorder(Node*root) {
if (root == NULL) return;
pre.push_back(root->data);
preorder(root->lchild);
preorder(root->rchild);
} void mirrBST(Node*root) {
if (root == NULL)return;
pre_mirr.push_back(root->data);
mirrBST(root->rchild);
mirrBST(root->lchild);
} void postorder(Node*root) {
if (root == NULL)return;
postorder(root->lchild);
postorder(root->rchild);
post.push_back(root->data);
} void postmirrorder(Node*root) {
if (root == NULL)return;
postmirrorder(root->rchild);
postmirrorder(root->lchild);
post_mirr.push_back(root->data);
}
int main() {
int n;
int temp;
cin >> n;
vector<int>v;
for (int i = ; i < n; i++) {
cin >> temp;
v.push_back(temp);
}
Node*root = createBST(v);
preorder(root);
mirrBST(root);
if (v == pre) {
postorder(root);
cout <<"YES"<<endl<< post[];
for (int i = ; i < post.size(); i++)
cout <<' '<< post[i];
cout << endl;
}
else if (v == pre_mirr) {
postmirrorder(root);
cout << "YES" << endl << post_mirr[];
for (int i = ; i < post_mirr.size(); i++)
cout << ' ' << post_mirr[i];
cout << endl;
}
else cout << "NO" << endl;
return ;
}
【PAT】1043 Is It a Binary Search Tree(25 分)的更多相关文章
-
PAT 1043 Is It a Binary Search Tree (25分) 由前序遍历得到二叉搜索树的后序遍历
题目 A Binary Search Tree (BST) is recursively defined as a binary tree which has the following proper ...
-
PAT 甲级 1043 Is It a Binary Search Tree (25 分)(链表建树前序后序遍历)*不会用链表建树 *看不懂题
1043 Is It a Binary Search Tree (25 分) A Binary Search Tree (BST) is recursively defined as a bina ...
-
1043 Is It a Binary Search Tree (25分)(树的插入)
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following propertie ...
-
【PAT甲级】1043 Is It a Binary Search Tree (25 分)(判断是否为BST的先序遍历并输出后序遍历)
题意: 输入一个正整数N(<=1000),接下来输入N个点的序号.如果刚才输入的序列是一颗二叉搜索树或它的镜像(中心翻转180°)的先序遍历,那么输出YES并输出它的后序遍历,否则输出NO. t ...
-
PAT甲级:1064 Complete Binary Search Tree (30分)
PAT甲级:1064 Complete Binary Search Tree (30分) 题干 A Binary Search Tree (BST) is recursively defined as ...
-
PAT 1043 Is It a Binary Search Tree[二叉树][难]
1043 Is It a Binary Search Tree(25 分) A Binary Search Tree (BST) is recursively defined as a binary ...
-
PAT Advanced 1043 Is It a Binary Search Tree (25) [⼆叉查找树BST]
题目 A Binary Search Tree (BST) is recursively defined as a binary tree which has the following proper ...
-
PAT (Advanced Level) 1043. Is It a Binary Search Tree (25)
简单题.构造出二叉搜索树,然后check一下. #include<stdio.h> #include<algorithm> using namespace std; +; st ...
-
PAT甲题题解-1043. Is It a Binary Search Tree (25)-二叉搜索树
博主欢迎转载,但请给出本文链接,我尊重你,你尊重我,谢谢~http://www.cnblogs.com/chenxiwenruo/p/6789220.html特别不喜欢那些随便转载别人的原创文章又不给 ...
-
PAT 1043 Is It a Binary Search Tree
#include <cstdio> #include <climits> #include <cstdlib> #include <vector> co ...
随机推荐
-
Html 之菜单导航(二)
网页菜单 网页菜单是一个网页的重要部分,它提供了用户可以对网站所有页面的导航,也是可能是内容的分类,例如淘宝 衣服 鞋子 水果 电脑 等等之类,也可以是 类似于游戏宣传网页一样子,酷炫的js特效 f ...
-
修改ORACLE-NLS_DATE_FORMAT时间格式的四种方式
修改ORACLE-NLS_DATE_FORMAT时间格式的四种方式 改变ORACLE -NLS_DATE_FORMAT中时间显示格式的显示有以下方式: 1.可以在用户环境变量中指定(LINUX). 在 ...
-
Qt Chart 5.7.0 傻瓜安装教程
前提 qtchart 里的README文件(注意红色标记处)(本人翻译不行.多多见谅,也可以在评论里纠正( ⊙ o ⊙ )) --------------- Qt Charts 5.7.0 ----- ...
-
[转]Pig与Hive 概念性区别
Pig是一种编程语言,它简化了Hadoop常见的工作任务.Pig可加载数据.表达转换数据以及存储最终结果.Pig内置的操作使得半结构化数据变得有意义(如日志文件).同时Pig可扩展使用Java中添加的 ...
-
【完整资料】TC358779XBG:HDMI转MIPI DSI芯片方案
TC358779XBG是一颗HDMI1.4转MIPI DSI带缩放功能的芯片,分辨率1920*1080,封装BGA80.通信方式:IIC,电源3.3/1.8/2.2,应用领域:平板,广告机,VR,显 ...
-
[Spark][kafka]kafka 的topic 创建和删除试验
kafka 的topic 创建和删除试验 zookeeper和kafka 的安装,参考: http://www.cnblogs.com/caoguo/p/5958608.html 参考上述URL后,在 ...
-
Django相关面试题
Django框架的生命请求周期 浏览器上输入地址,回车然后发生了什么? => Http请求生命周期 ? 什么是wsgi 以及作用? 中间件 中间件的执行流程? 中间件的执行流程? 说一下Djan ...
-
点击当前选项显示当前内容jquery
<script language="javascript"> $(document).ready(function(){ $(".moren a") ...
-
通过javascript添加一行
<html><head> <title>添加新的行</title></head><body> <div onclick=& ...
-
JMeter学习笔记--JMeter属性和变量
JMeter属性统一定义在jmeter.properties文件中.JMeter属性在测试脚本的任何地方都是可见的(全局),通常被用来定义一些JMeter使用的默认值.如属性remote_hosts定 ...