# 【PAT甲级】Is It a Binary Search Tree

### Problem Description：

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```

`NO`

### AC代码：

```#include <bits/stdc++.h>
using namespace std;

typedef struct TreeNode
{
int data;   //结点值
TreeNode *lchild,*rchild;   //左右子树
}*Tree;

void insert(Tree &root,int x)    //构造二叉搜索树
{
if(root == NULL)   //若根结点为空则新建一个根结点值为x的二叉树
{
root = new TreeNode;
root->data = x;
root->lchild = root->rchild = NULL;
}
else if(x < root->data)   //若x小于根结点的值则把插入到左子树
{
//二叉搜索树的左子树上的结点值都小于根结点的值
insert(root->lchild,x);
}
else   //否则将x插入到右子树
{
//二叉搜索树的右子树上的结点值都大于根结点的值
insert(root->rchild,x);
}
}

void preOrder(Tree root, vector<int> &pre)    //把二叉树先序遍历(中左右)的结果放入vector中
{
if(root == NULL) return;
pre.push_back(root->data);
//cout << root->data << " ";
preOrder(root->lchild,pre);
preOrder(root->rchild,pre);
}

void postOrder(Tree root, vector<int> &post)    //把二叉树后序遍历(左右中)的结果放入vector中
{
if(root == NULL) return;
postOrder(root->lchild,post);
postOrder(root->rchild,post);
post.push_back(root->data);
//cout << root->data << " ";
}

void print(vector<int> &v)   //输出vector
{
bool isVirgin = true;   //判断是不是第一次
for(auto it : v)
{
if(isVirgin)    //第一次直接输出数字
{
printf("%d",it);
isVirgin = false;
}
else     //如果不是第一次了,则每次输出数字前先输出一个空格
{
printf(" %d",it);
}
}
printf("\n");
}

void reverse(Tree root)     //二叉树的反转
{
if(root == NULL) return;
swap(root->lchild,root->rchild);
reverse(root->lchild);
reverse(root->rchild);
}

int main()
{
int N;   //结点数N
cin >> N;
Tree bt = NULL;    //创建二叉树
vector<int> v,pre,post;   //原始序列v、先序遍历序列pre、后序遍历序列post
for(int i = 0; i < N; i++)
{
int temp;
cin >> temp;
insert(bt,temp);   //构建二叉搜索树
v.push_back(temp);
}
preOrder(bt,pre);  //得到先序序列pre
if(pre == v)   //若原始序列和先序序列相等,则说明bt是二叉搜索树
{
printf("YES\n");
postOrder(bt,post);    //得到后序序列post
print(post);
}
else
{
reverse(bt);   //把二叉搜索树进行反转,得出二叉搜索树的镜像
pre.clear();   //清空先序序列
preOrder(bt,pre);   //得到二叉搜索树的镜像的先序序列
if(pre == v)
{
printf("YES\n");   //得到二叉搜索树的镜像的后序序列post
postOrder(bt,post);
print(post);
}
else
{
printf("NO\n");
}
}
return 0;
}```

0 条评论

• ### 【Codeforces】1217A - Creating a Character

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 【GPLT】L1-007 念数字

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 【AI专栏】语音合成系统评测介绍

如何从多维度评价TTS系统质量成了TTS测试人员的一大挑战。本文针对TTS前端、后端的问题介绍了一种包括主观评测、客观评测TTS测试方法。

• ### 跳图嵌入中与语义和语法相关的子向量（CS CompLang）

我们研究出任何单词的跳图语法嵌入都可以分解为两个子向量，它们大致对应于单词的语义和句法作用。

• ### linux下MBR分区表修复/恢复

主引导记录（Master Boot Record，MBR），位于一个硬盘的0柱面、0盘面、1扇区，共512字节。具体划分依次为：引导代码区440字节、磁盘签名4...

• ### Android Activity生命周期整理

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 串口+RS485驱动

其实RS485不算什么协议，只是物理层做了差分传输，AB两线的电压差来表示0，1，0，1，可靠性和距离更加好，因此，一个串口外设只能作为半双工使用，而RS232...

• ### Cephfs的快照功能

Cephfs的快照功能在官网都很少提及，因为即使开发了很多年，但是由于cephfs的复杂性，功能一直没能达到稳定，这里，只是介绍一下这个功能，怎么使用，并且建议...