【GPLT 二阶题目集】L2-004 这是二叉搜索树吗？

参考文章：L2-004. 这是二叉搜索树吗？-PAT团体程序设计天梯赛GPLT   作者：柳婼（非常感谢!!!）

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

        其左子树中所有结点的键值小于该结点的键值；
        其右子树中所有结点的键值大于等于该结点的键值；
        其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例1：

7
8 6 5 7 10 8 11

输出样例1：

YES
5 7 6 8 11 10 8

输入样例2：

7
8 10 11 8 6 7 5

输出样例2：

YES
11 8 10 7 5 6 8

输入样例3：

7
8 6 8 5 10 9 11

输出样例3：

NO

#include <iostream>
#include <vector>
using namespace std;vector<int> preOrder; //前序遍历序列
vector<int> postOrder; //后序遍历序列
int n;
bool mirror = false; //是否镜像搜索void creatBiTree(int pl, int pr) //搜索树建立
{if (pl > pr) return;else if (pl == pr) {postOrder.push_back(preOrder[pl]);return;}int l = pl + 1, r = pr;if (!mirror){while (l <= pr && preOrder[l] < preOrder[pl])l++;while (r > pl && preOrder[r] >= preOrder[pl])r--;}else{while (l <= pr && preOrder[l] >= preOrder[pl])l++;while (r > pl && preOrder[r] < preOrder[pl])r--;}if (l - r != 1) return;creatBiTree(pl + 1, r);creatBiTree(l, pr);postOrder.push_back(preOrder[pl]);return;
}int main()
{int temp; cin >> n;for (int i = 0; i < n; i++) {cin >> temp;preOrder.push_back(temp);}creatBiTree(0, n - 1);if (postOrder.size() != n){mirror = true;postOrder.clear();creatBiTree(0, n - 1);}if (postOrder.size() == n){cout << "YES" << endl << postOrder[0];for (int i = 1; i < n; i++)cout << " " << postOrder[i];cout << endl;}elsecout << "NO" << endl;return 0;
}

注意事项：

不知道为什么下面的代码有两个测试点一直过不去……

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;vector<int> preOrder;
int n, counts = 0;
bool res1 = true, res2 = true;typedef struct biTreeNode { //定义二叉树结点int key;biTreeNode* lchild;biTreeNode* rchild;
}biTree, * BiTree;void creatBiTree1(BiTree &T,int pl,int pr) //正常搜索树建立
{if (pl <= pr && res1 == true) {T = (BiTree)malloc(sizeof(biTreeNode));int ll = pl + 1, rl = pl + 1 , lr = pr, rr = pr;T->key = preOrder[pl];for (int i = pl + 1; i <= pr; i++) {if (preOrder[i] < T->key) {ll = i; break; //找到第一个比key小的键值}else if (i == pr) {T->lchild = NULL;}}for (int i = pl + 1; i <= pr; i++) {if (preOrder[i] >= T->key) {lr = i - 1, rl = i;break; //找到第一个比key大或相等的键值}else if (i == pr) {T->rchild = NULL;}}for (int i = rl; i <= rr; i++) {if (preOrder[i] < T->key) {res1 = false; break; //判断右子树序列中是否有非法值}}creatBiTree1(T->lchild, ll, lr);creatBiTree1(T->rchild, rl, rr);}else T = NULL; return;
}void creatBiTree2(BiTree& T, int pl, int pr) //镜像搜索树建立
{if (pl <= pr && res2 == true) {T = (BiTree)malloc(sizeof(biTreeNode));int ll = pl + 1, rl = pl + 1, lr = pr, rr = pr;T->key = preOrder[pl];for (int i = pl + 1; i <= pr; i++) {if (preOrder[i] >= T->key) {ll = i;break; //找到第一个比key大或相等的键值}else if (i == pr) {T->lchild = NULL;}}for (int i = pl + 1; i <= pr; i++) {if (preOrder[i] < T->key) {lr = i - 1, rl = i;break; //找到第一个比key小的键值}else if (i == pr) {T->rchild = NULL;}}for (int i = rl; i <= rr; i++) {if (preOrder[i] >= T->key) {res2 = false; break; //判断右子树序列中是否有非法值}}creatBiTree2(T->lchild, ll, lr);creatBiTree2(T->rchild, rl, rr);}else T = NULL;return;
}void postPrint(BiTree T) {if (T) {postPrint(T->lchild);postPrint(T->rchild);cout << T->key; counts++;if (counts < n) cout << " ";else cout << endl;}else return;
}int main()
{int temp; cin >> n;for (int i = 0; i < n; i++) {cin >> temp; preOrder.push_back(temp);}BiTree head1, head2;creatBiTree1(head1, 0, n - 1);creatBiTree2(head2, 0, n - 1);if (res1) {cout << "YES" << endl;postPrint(head1);}else if (res2) {cout << "YES" << endl;postPrint(head2);}else cout << "NO" << endl;return 0;
}

二阶题完结撒花！！！

如有问题，欢迎提出。