专栏首页vblogPAT 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 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

题目解读

给定一个输入序列,判断它是否是一棵二叉搜索树或其镜像树的前序遍历序列,如果是,输出 YES 以及它的后序遍历序列;如果不是,输出 NO。

二叉搜索树的定义:

  • 左子树所有节点的键值小于根节点
  • 右子树所有节点的键值大于等于根有点
  • 左子树和右子树也必须是二叉搜索树(满足上面两点)

镜像树:交换原二叉搜索树每个节点的左右子树。所以它满足:

  • 左子树所有节点的键值大于等于根节点
  • 右子树所有节点的键值小于根有点
  • 左子树和右子树也必须满足上面两点

首先我们应该明白一个道理:

一般情况下,我们要根据一棵二叉树的前序遍历结果和中序遍历结果才能得到它的后序遍历结果,但这里为什么只需要前序遍历结果就可以得到后序遍历结果?

二叉搜索树又叫二叉排序树,由它的定义就知道它本身是有序的,对一棵二叉搜索树进行中序遍历,得到就是一个非降序有序序列,这也可以作为一种排序方法。

所以如果给出的序列的确是一棵二叉搜索树的前序遍历的话,对它进行一次排序就能得到它的中序遍历结果,前序+中序就能得到后序,所以需要明白这个隐含条件。

思路分析

你可以选择用给出的输入构造出一棵二叉搜索树,然后再对这棵树进行前序遍历,判断得到的结果是否和输入一致,如果不一致,那就输出 NO,如果一致就输出这这棵树的后序遍历结果。

我这里参考了柳神的代码,采用了一种更为简单的方法。

可以想象一下,根据 前序遍历结果和中序遍历结果能得到正确的后序遍历结果,那,如果给出的前序结果是错误的呢(它不是一棵二叉搜索树的前序结果),那肯定不能得到正确的后序遍历结果,假如我用一个vector来保存在此过程中得到的节点序列,那么最终这个vector中的节点个数肯定不够原来输入的个数(当然前提是算法正确)。

所以我们可以假设这个输入序列是对的,然后利用这个输入序列去得到后序序列并保存,如果最终得到的结果中节点个数不够,那说明它不是正确的前序遍历,否则就直接输出得到的结果

当然这里还多了一步,如果把它当作前序遍历序列不能得到正确结果,我们还要把它当作二叉搜索树的镜像树的前序结果再执行一次这个过程,如果这次还不能得到正确结果,那说明它的确是错误的前序序列。

接下来我们来研究一下这个算法怎么写:

对于一棵二叉搜索树,因为它的有序性,对他进行前序遍历(根,左子树,右子树),得到的序列肯定满足这个样子:根节点 所有比它小的节点 所有比它的大的节点

比如下面这棵二叉搜索树

它的前序遍历结果是 8 567 91011,是不是很有特点,我们能根据这个很好的划分出它的左右子树:

  • 当前树根是8,设置左指针i,初始是8的下一个位置,右指针j,初始是当前树最后一个有效位置
  • i从左往右,扫描前序序列,遇到比根小的就i++,会停在9的位置;
  • j从右往左,扫描前序序列,遇到比根大于或等于的就j--,最后会停在7的位置
  • 这样一次扫描后,应该满足 j + 1 == i,对于每一个二叉搜索树的前序遍历都应该满足这个特点,所以这里可以作为函数的一个出口,不满足,就退出
  • 划分成左右两部分后,因为我们要得到后序遍历(左,右,中),所以对做左子树进行这个处理,对右子树进行这个处理,把当前树根加入vector,注意顺序不能乱!

从上面可以看出:

  • 这个函数需要两个参数,一个是当前树的根,一个是当前树最后一个节点在前序序列中的位置
  • 每次双指针扫描结束后,不满足 i == j + 1 就退出
  • 最小的子树是只有一个节点,此时这两个参数应该相等,所以函数刚进来的时候,判断一个,如果根的位置 > 最后一个有效位置,就直接退出。

上面的过程是针对于 把输入序列当作二叉搜索树的前序遍历进行的,如果要把输入序列当作镜像树的前序遍历序列呢?很简单,根据对称性,只需要把 i 和 j 的扫描时的判断条件取个反就行了,也就是 > 变成 <=> 变成 <=.

所以你可以写成两个函数分别处理这两种情况,也可以设置一个标志在函数内部分情况,我选择第二种,直接看代码很清楚。

综上,总体执行流程为:

  • 把输入序列当作二叉搜索树前序遍历,执行这个函数,得到后序结果,
  • 如果所得结果中节点个数与输入一致,直接输出
  • 如果不一致,把输入序列当作二叉搜索树镜像树的前序遍历,也就是改变标志位,再执行一次这个函数,得到后序结果
  • 再判断所得结果中节点个数是否与输入一致,一致则输出,不一致则输出 NO。

完整代码

#include<iostream>
#include<vector>
using namespace std;
// 前序遍历序列,后序遍历序列
vector<int> pre, post;
// 是否当作二叉搜索树的镜像树处理
bool ismirror = false;

// 当前处理的树的根节点在前序序列中的下标
// 当前处理的树最后一个节点在前序序列中的有效位置
void GetPost(int root, int tail) {
    // 最小的树就一个节点,root=tail
    if (root > tail) return;
    int i = root + 1, j = tail;
    // 当作二叉搜索树树处理
    if (!ismirror) {
        // 左孩子都小于根
        while (i <= tail && pre[i] < pre[root]) i++;
        // 右孩子都大于等于根
        while (j > root && pre[root] <= pre[j]) j--;
    // 当作二叉搜索树的镜像树处理
    } else {
        // 左孩子都大于等于根
        while (i <= tail && pre[i] >= pre[root]) i++;
        // 右孩子都小于根
        while (j > root && pre[root] > pre[j]) j--;
    }
    // 不满足二叉搜索树前序遍历结果特点
    if (i != j + 1) return;
    // 对左子树执行此操作
    GetPost(root + 1, j);
    // 对右子树执行此操作
    GetPost(i, tail);
    // 保存当前根
    post.push_back(pre[root]);
}

int main() {
    int n;
    cin >> n;
    pre.resize(n);
    for (int i = 0; i < n; ++i) cin >> pre[i];
    // 当作前序遍历结果,尝试得到后序结果
    GetPost(0, n - 1);
    // 所得结果节点个数错误
    if (post.size() != n) {
        // 改变标志位
        ismirror = true;
        post.clear();
        // 当作镜像树前序遍历结果,尝试获取后序结果
        GetPost(0, n - 1);
    }
    // 所得结果正确
    if (post.size() == n) {
        cout << "YES" << endl;
        cout << post[0];
        for (int i = 1; i < n; ++i) cout << " " << post[i];
    // 所得结果依然错误
    } else {
        cout << "NO";
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT 1003 Emergency (25分) Dijstra

    As an emergency rescue team leader of a city, you are given a special map of you...

    vivi
  • PAT 1048 Find Coins (25分) 硬币面值做数组下标即排序

    Eva loves to collect coins from all over the universe, including some other plan...

    vivi
  • PAT 1051 Pop Sequence (25分) 模拟入栈

    Given a stack which can keep M numbers at most. Push N numbers in the order of 1...

    vivi
  • Python知识梳理

    我们可以使用type()函数类获取对象的类型,Python3中内置数据类型包括:None,int,float,complex,str,list,dict,tup...

    雪飞鸿
  • 企业CIO在移动信息化建设中思考?

    自从离开媒体圈以来,已经有三四年没有涉足CIO这个圈子,就象陶渊明笔下的《桃花源记》一样” 自云先世避秦时乱,率妻子邑人,来此绝境,不复出焉;遂与外人间隔。问今...

    人称T客
  • 企业信息化的变与不变之间,为何新技术成为阻碍CIO前进的绊脚石?| 研报

    撰文 | 杨丽 互利网时代,企业信息化似乎迫在眉睫。CIO们在苦苦冥思,2017年究竟哪些领域才是企业信息化的重点,又会在哪些技术领域出现颠覆性的技术转型?随...

    人称T客
  • 介绍新的 GitLab 分支源插件

    GitLab 分支源插件已经走出 beta 阶段,并已发布到 Jenkins 更新中心。它允许您基于 GitLab 用户 或 组 或 子组 项目创建任务。您可以...

    LinuxSuRen
  • 手把手教你如何重建二叉树(超精彩配图)

    输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    TrueDei
  • React-Redux 源码解析系列 -- React-Redux的作用

    前面的章节讲完了redux的部分,又已经有了react,那为什么还需要有React-Redux呢?这个React-Redux 又帮助我们做了什么呢? conte...

    IMWeb前端团队
  • React-Redux 源码解析系列 -- React-Redux的作用

    前面的章节讲完了redux的部分,又已经有了react,那为什么还需要有React-Redux呢?这个React-Redux 又帮助我们做了什么呢?

    IMWeb前端团队

扫码关注云+社区

领取腾讯云代金券