【刷算法】判断二叉搜索树的后序遍历序列的递归实现和非递归实现

Anshiii 发布于2019-08-22 18:20 / 1996人阅读

摘要：题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。那么对于二叉搜索树的后序遍历的序列来说，最后一个元素即是它的根节点，序列的前某部分元素全部小于最后一个元素，序列的后某部分元素全大于最后一个元素。

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

分析

所谓二叉搜索树，也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

任意节点的左、右子树也分别为二叉查找树；

没有键值相等的节点。

那么对于二叉搜索树的后序遍历的序列来说，最后一个元素即是它的根节点，序列的前某部分元素全部小于最后一个元素，序列的后某部分元素全大于最后一个元素。然后对于这两部分来说，又分别符合这些特点，可以递归的检查下去。

递归实现

function VerifySquenceOfBST(s)
{
    if(s.length === 0)
        return false;
    return judge(s, 0, s.length-1);
}

function judge(a, l, r) {
    if(l >= r)
        return true;
    var p1 = r;
    while(p1 > l && a[p1-1] > a[r]) {
        p1--;
    }
    var p2 = p1-1;
    while(p2 >= l){
        if(a[p2] > a[r])
            return false;
        p2--;
    }
    
    return judge(a, l, p1-1) && judge(a, p1, r-1);
}

非递归实现

对于一个二叉搜索树来说，根节点的左子树每个节点的值肯定小于右子树每个节点的值，所以可以不断的去去掉序列的最后一个值，并且把剩下的部分分成小于最后一个值和大于最后一个值的两部分，只要能分出来那就说明符合二叉搜索树的定义，否则就不符合。

function VerifySquenceOfBST(s)
{
    if(s.length === 0)
        return false;
    var start = 0, end = s.length-1;
    while(end !== 0) {
        while(s[start] < s[end]){
            start++;
        }
        while(s[start] > s[end]){
            start++;
        }
        
        if(start < end)
            return false;
        end--;
        start  = 0;
    }
    return true;
    
}

GPU云服务器云服务器非递归二叉树遍历二叉树的遍历 php树的递归查询 python实现递归

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95761.html

树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

RaoMeng 2019-08-19 11:08 评论0 收藏0
树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

PiscesYE 2019-07-30 17:45 评论0 收藏0
二叉树遍历

摘要：前言本篇文章是在二叉排序树的基础上进行遍历查找与删除结点。接下来我们根据构造的这颗二叉树进行相应遍历查找与删除操作。遍历二叉树二叉树的遍历分为深度优先遍历和广度优先遍历。中序遍历二叉排序树，得到的数组是有序的且是升序的。前言本篇文章是在二叉排序树的基础上进行遍历、查找、与删除结点。那么首先来看一下什么是二叉排序树？二叉排序树定义二叉排序树，又称二叉查找树、二叉搜索树。若...

aboutU 2019-08-26 13:54 评论0 收藏0