PAT甲级真题 1043 Is It a Binary Search Tree (25分) C++实现（二叉搜索树，递归前序转后序）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了PAT甲级真题 1043 Is It a Binary Search Tree (25分) C++实现（二叉搜索树，递归前序转后序），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3570字，纯文字阅读大概需要6分钟。
内容图文
题目
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：
7
8 6 5 7 10 8 11
可成功划分为：
接着继续划分左右子树，均符合要求。
再看测试用例3：
7
8 6 8 5 10 9 11
以第一个元素8为根，小于它的元素时6、5，大于等于它的元素是8、10、9、11，第一次划分就失败了。
具体方法
- 检查是否是二叉搜索树，按照
根 左子树 右子树的方式迭代划分序列，若发现不符合要求的，返回false；若一直符合要求，则输出YES，输出其后序遍历数列。 - 再检查是否是镜像二叉搜索树，按照
根 右子树 左子树的方式迭代划分序列，若发现不符合要求的，直接输出“No”；若一直符合要求，则输出YES，输出其后序遍历数列。
这里学习了柳神的方法：
- 检查序列的同时，将后序序列保存到post数组
- 若符合要求则递归检查其左子树和右子树，最后把根节点加入post数组；若不符合要求直接返回。
- 最后检查post数组元素个数是否等于n，即可知是否符合要求。
代码
#include <iostream>
#include <vector>
using namespace std;
void getPost(vector<int> pre, int l, int r, vector<int> &post, bool isMirror){
if (l==r){
post.push_back(pre[l]);
}
else if(l < r){
int i = l + 1;
int j = r;
if (!isMirror){
while(i<=r && pre[i]<pre[l]) i++;
while(j>l && pre[j]>=pre[l]) j--;
}
else{
while(i<=r && pre[i]>=pre[l]) i++;
while(j>l && pre[j]<pre[l]) j--;
}
if (j < i){
getPost(pre, l+1, j, post, isMirror);
getPost(pre, i, r, post, isMirror);
post.push_back(pre[l]);
}
}
return;
}
int main(){
int n;
cin >> n;
vector<int> pre(n);
for(int i = 0; i < n; i++){
cin >> pre[i];
}
vector<int> post;
getPost(pre, 0, n-1, post, false);
if (post.size()<n){ //若假设是二叉搜索树不成立
post.clear();
getPost(pre, 0, n-1, post, true);
}
if(post.size()<n){ //若假设是镜像二叉搜索树仍不成立
cout << "NO" << endl;
}
else{
cout << "YES" << endl;
cout << post[0];
for (int i=1; i<n; i++){
cout << " " << post[i];
}
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的PAT甲级真题 1043 Is It a Binary Search Tree (25分) C++实现（二叉搜索树，递归前序转后序）全部内容，希望文章能够帮你解决PAT甲级真题 1043 Is It a Binary Search Tree (25分) C++实现（二叉搜索树，递归前序转后序）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。