【PAT甲级】Is It a Binary Search Tree

喜欢ctrl的cxk

发布于 2019-11-08 15:45:30

3200

发布于 2019-11-08 15:45:30

文章被收录于专栏：Don的成长史

本文链接：https://blog.csdn.net/weixin_42449444/article/details/90143012

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

Sample Output 3:

NO

解题思路：

这道题考察到了很多关于树的知识，比如：①二叉搜索树的定义及构造；②二叉树的先序遍历、后序遍历；③二叉树的反转；④如何判断一颗二叉树是不是二叉搜索树。

用一个vector（原始序列v）来保存输入的先序遍历序列。根据输入的原始序列来构建一棵二叉搜索树bt，调用自定义函数preOrder()来得到二叉搜索树bt的先序遍历序列pre。一共有三种情况：①若先序序列pre和原始序列v相等就说明这是一棵二叉搜索树，输出"YES"并调用自定义函数postOrder()来得到二叉搜索树bt的后序遍历序列post，最后输出post即可；②若pre和v不相等，则调用自定义函数reverse()来将二叉搜索树的左右子树进行反转从而得到它的镜像，然后调用preOrder()来得到二叉搜索树镜像的先序遍历序列pre，若pre和v相等说明这是二叉搜索树的镜像，输出"YES"并调用自定义函数postOrder()来得到二叉搜索树镜像的后序遍历序列post，最后post即可；③如果既不是一棵二叉搜索树，也不是一棵二叉搜索树的镜像就输出"NO"。

解释一下这些自定义函数：我们都知道二叉搜索树的左子树的结点值都小于根结点的值，二叉搜索树的右子树的结点值都大于根结点的值，那么就可以根据这个性质来递归构造二叉搜索树：若二叉树根结点为空则新建一个根结点值为x的二叉树，若x小于根结点的值则插入到左子树，若x不小于根结点的值则插入到右子树。先序遍历和后序遍历这俩个自定义函数就不解释啦。反转二叉树这个自定义函数，我是通过无脑递归交换左右子树来实现的。

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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/05/12 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法