首页 > 试题广场 >

二叉搜索树的后序遍历序列

[编程题]二叉搜索树的后序遍历序列
  • 热度指数：870656 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。

数据范围： 节点数量 ，节点上的值满足 ，保证节点上的值各不相同
要求：空间复杂度 ，时间时间复杂度
提示：
1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
2.该题我们约定空树不是二叉搜索树
3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
4.参考下面的二叉搜索树，示例 1

示例1

输入

[1,3,2]

输出

true

说明

是上图的后序遍历 ，返回true
示例2

输入

[3,1,2]

输出

false

说明

不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列 ，因为最后的2一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是[3,1,2]的组合都不能满足这些情况，故返回false
示例3

输入

[5,7,6,9,11,10,8]

输出

true
算法知识视频讲解
添加回答
推荐
马客(Mark)头像 马客(Mark)
BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 : ) 。 

class Solution {
    bool judge(vector<int>& a, int l, int r){
        if(l >= r) return true;
        int i = r;
        while(i > l && a[i - 1] > a[r]) --i;
        for(int j = i - 1; j >= l; --j) if(a[j] > a[r]) return false;
        return judge(a, l, i - 1) && (judge(a, i, r - 1));
    }
public:
    bool VerifySquenceOfBST(vector<int> a) {
        if(!a.size()) return false;
		return judge(a, 0, a.size() - 1);
    }
};

编辑于 2015-09-24 10:51:14 回复(148)
Python
归海迎夏头像 归海迎夏
class Solution:
    def depth(self, sequence, right, left):
        if left<right:
            return True
        i = left
        while i>right and sequence[left]<sequence[i-1]:
            i-=1
        for j in range(right,i-1):
            if sequence[left]<sequence[j]:
                return False
        return self.depth(sequence,0,i-1) and self.depth(sequence,i,left-1)
    
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence) == 0:
            return False
        if len(sequence) == 1:
            return True
        return self.depth(sequence,0,len(sequence)-1)
发表于 2021-09-15 07:07:54 回复(0)
Python
张洪路头像 张洪路 
def verifySquenceOfBST(nums):
    size = len(nums)
    if(size == 0):
        return False
    
    def helper(nums, start, end):
        # nums 在区间[start, end]   
        if(start > end):
            return True
        
        root_val = nums[end]
        
        pos = start
        # 找到左孩子
        for i in range(start, end):   
            if(nums[i] > root_val):
                pos = i
                break
            
        # 判断右孩子是否满足大于根节点
        for j in range(pos, end):
            if(nums[j] < root_val):
                return False
        
        left,right = True, True
        left = helper(nums, start, pos-1)
        right = helper(nums, pos, end-1)
        
        return left and right
    
    return helper(nums, 0, size-1)

发表于 2021-05-24 16:40:53 回复(0)
Python
Quinn_5400头像 Quinn_5400
一.后续遍历的特点     :左->右->跟
二.二叉搜索树的特点 :左子树小于跟小于右子树
三.设计到树通常是一组最简单的单元判断,然后递归子节点
四.空子树不是二叉搜索树,没有子节点的树判断为二叉搜索树

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence) == 1:
            return True
        # 空子树不是搜索二叉树
        if len(sequence) == 0:
            return False
        root = sequence[-1]
        # 根据跟节点划分左右子树
        idx_root = 0
        for v in sequence:
            if v < root:
                idx_root += 1
        # 判断左右子树是否满足左侧小于跟节点,右侧大于跟节点的规则
        ## 左子树已经判断,这里直接对右子树做存在性和合法性判断
        if idx_root < len(sequence)-1 and root > min(sequence[idx_root:-1]):
            return False
        # 左右子树的判断
        r_left = True
        r_right = True
        if idx_root > 0:
            r_left = self.VerifySquenceOfBST(sequence[:idx_root])
#         else:
#             r_left = True
        if idx_root < len(sequence)-1:
            r_right = self.VerifySquenceOfBST(sequence[idx_root:-1])
#         else:
#             r_right = True
        # 如果左右子树都是后续遍历的二叉搜索树、则整体都是
        return r_left and r_right
发表于 2021-04-27 14:07:44 回复(0)
Python
牛客383802969号头像 牛客383802969号
python中   if not sequece   与 if sequece==None 有啥区别呢？有的地方可以互换用，但是这个程序中互换了就出错。 
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:    #  这里改成  sequerce== None 就错了
            return False
        root = sequence[-1]
        # 根据根结点将左右子树的分界线找到
        i = 0
        while i<len(sequence)-1:
            if sequence[i]>root:
                break
            i += 1
        
        # 判断右子树中是否都大于root
        for j in range(i, len(sequence)-1):
            if sequence[j]<root:
                return False
        
        left = True
        right = True
        if i>0:
            left = self.VerifySquenceOfBST(sequence[:i])
        if i<len(sequence)-1:
            right = self.VerifySquenceOfBST(sequence[i:len(sequence)-1])
            
        return left and right
        


发表于 2021-03-25 09:42:54 回复(0)
Python
老和山小学生头像 老和山小学生 
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        return self.VerifySeq(sequence)
    def VerifySeq(self, sequence):
        if not sequence:
            return True
        root = sequence[-1]
        for i in range(len(sequence)):
            if sequence[i] < root:
                i += 1
            else:
                break
        for j in range(i, len(sequence)-1):
            if sequence[j] <= root:
                return False
        return self.VerifySeq(sequence[:i]) and self.VerifySeq(sequence[i:-1])

发表于 2020-10-13 15:02:36 回复(0)
Python
月亮surperman头像 月亮surperman
搜索二叉树，排序二叉树，后序遍历左右根。
只需要考虑一个问题，就是出现大于根的数之后，不能再出现任何一个小于该根的数。
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        a = sequence[-1]
        for i in range(len(sequence)-1):
            if sequence[i] > a and sequence[i+1] < a:
                return False
        return True

发表于 2020-08-15 21:19:45 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        root = sequence[-1]
        length = len(sequence)
        for i in range(length):
            if sequence[i] > root:
                break
        
        for j in range(i,length):
            if sequence[j] < root:
                return False
        left = right = True
        if i > 0:
            left = self.VerifySquenceOfBST(sequence[:i])
        if i < length -1:
            right = self.VerifySquenceOfBST(sequence[i:-1])
        return left and right
python:后序遍历 的序列中，最后一个数字是树的根节点 ，数组中前面的数字可以分为两部分：第一部分是左子树节点 的值，都比根节点的值小；第二部分 是右子树 节点的值，都比 根 节点 的值大，后面用递归分别判断前后两部分 是否 符合以上原则
发表于 2020-08-06 15:20:29 回复(0)
Python
sk8_wt头像 sk8_wt 
class Solution:
    flag_ = True
    def VerifySquenceOfBST(self, sequence):
        if len(sequence)<=1:
            return sequence
        root = sequence[-1]
        index = 0
        for i in range(len(sequence)-1):
            index = i
            if sequence[i]>root:
                index = i-1
                break
        left_list = sequence[:index+1]
        right_list = sequence[index+1:-1]
        print(left_list,right_list)
        if (right_list and min(right_list)<=root)&nbs***bsp;(left_list and max(left_list)>=root):
            self.flag_ = False
            return
        self.VerifySquenceOfBST(left_list)
        self.VerifySquenceOfBST(right_list)
        return self.flag_

每个数组的最后一个数，能够找到一个‘大于左边所有数、小于右边所有数’的位置，
不满足该条件则不是后序遍历的结果
编辑于 2020-08-07 16:12:44 回复(0)
Python
橘子汽水超人2号头像 橘子汽水超人2号

Python Solution 

class Solution:
    def VerifySquenceOfBST(self, sequence):
        if len(sequence)<=1:return bool(sequence)
        left = [x for x in sequence if x<sequence[-1]]
        right = [x for x in sequence if x>sequence[-1]]
        if left+right+[sequence[-1]]!=sequence:return False
        else:
            return (left==[]&nbs***bsp;self.VerifySquenceOfBST(left)) and (right==[]&nbs***bsp;self.VerifySquenceOfBST(right))


编辑于 2020-06-01 15:53:24 回复(0)
Python
谢小橙头像 谢小橙 
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        # 正常来说，空树是二叉搜索树，应该返回True，但是这道题视作False
        if sequence == []:
            return False
        
        rootNum = sequence[-1] # 后序遍历的最后一个值为根节点的值
        del sequence[-1] # 删除掉根节点，只剩下左子树和右子树
        index = None
        for i in range(len(sequence)):
            if index == None and  sequence[i]>rootNum: # 寻找左右子树的分割线
                index = i
            if index != None and sequence[i]<rootNum: # 如果分割线的右边有比根节点小的数，说明不是二叉搜索树
                return False
        if sequence[:index] == []: # 空树是二叉搜索树
            return True
        else:
            leftRet=self.VerifySquenceOfBST(sequence[:index]) # 递归左子树
        
        if sequence[index:] == []: # 空树是二叉搜索树
            return True
        else:
            rightRet=self.VerifySquenceOfBST(sequence[index:]) # 递归右子树
            
        return leftRet and rightRet
编辑于 2020-04-18 22:06:13 回复(0)
Python
fregoco头像 fregoco 
class Solution:
    def VerifySquenceOfBST(self, sequence):
        if sequence == []:
            return False
        if len(sequence) == 1:
            return True
        i = 0#寻找左子树
        while sequence[i] < sequence[-1]:
            i += 1
        j = i#寻找右子树
        while sequence[j] > sequence[-1]:
            j += 1
        if j < len(sequence)-1:#右子树非全部小于根节点则判假
            return False
        if i == 0:#左子树为空
            return self.VerifySquenceOfBST(sequence[i: j])
        elif i == j: #右子树为空
            return self.VerifySquenceOfBST(sequence[ :i])
        else:#左右子树都存在
            return self.VerifySquenceOfBST(sequence[ :i]) and self.VerifySquenceOfBST(sequence[i: j])

编辑于 2020-04-15 20:47:27 回复(0)
Python
小马不再虎头像 小马不再虎
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        (3641)# write code here
        if len(sequence) == 0: return False
        return self.IsTreeBST(sequence,0,len(sequence)-1)
    def IsTreeBST(self,sequence,start,end):
        if start >= end: return True
        for i in range(start,end):
            if sequence[i] > sequence[end]:break
        for j in range(i,end-1):
            if sequence[j] < sequence[end]:return False
        return self.IsTreeBST(sequence,start,i-1) and self.IsTreeBST(sequence,i,end-1)
发表于 2020-03-25 14:42:33 回复(0)
Python
朝夕_头像 朝夕_ 
class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False
        elif len(sequence) == 1&nbs***bsp;len(sequence) == 2:
            return True
        else:
            for i in range(len(sequence)):
                if sequence[i] > sequence[-1]:
                    break
            if i < len(sequence)-1:
                if min(sequence[i:-1]) <= sequence[-1]:
                    return False
            if sequence:
                self.VerifySquenceOfBST(sequence[:i])
                self.VerifySquenceOfBST(sequence[i:-1])
            return True

发表于 2020-03-02 18:10:55 回复(0)
Python
牛客447097232号头像 牛客447097232号 
# -*- coding:utf-8 -*-
"""
1. 后序遍历最后一个节点时根节点
2. BST某一个节点x的左子树都小于x，x的右子树都大于x

"""
class Solution:
    def VerifySquenceOfBST(self, sequence):
        self.seq = sequence
        if not sequence:
            return False
        else:
            return self.check(0, len(sequence) - 1)

    def check(self,start,end):
        # one element or no element
        if end <= start:
            return True
        else:
            root = self.seq[end]
            # find the index of the first element that bigger than root
            for i in range(start, end):
                if self.seq[i] > root:
                    break
            # some elements bigger than root
            # [start,end)中当所有的元素都小于end时，i指向的是是end-1，是左子树的最后一个元素，而非右子树的第一个元素
            # 这时检测[end-1,end)是否有元素小于root实际是不对的
            if i < end - 1:
                for j in range(i,end):
                    # check if all elements bigger than root
                    if self.seq[j] <= root:
                        return False
                return self.check(start,i-1) and self.check(i,end-1)
            # all elements smaller than root
            else:
                return self.check(start,i-1)


s = Solution()
ans = s.VerifySquenceOfBST([7,4,6,5])
print(ans)
编辑于 2020-02-28 16:38:01 回复(0)
Python
牛客108916715号头像 牛客108916715号
python 递归：
不断把数组切成左右树，递归判断
昨天还不会递归来着。。。突然就会了。。。 
class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:return False
        #找到左右子树分界点
        for i in range(len(sequence)):
            if sequence[i]>=sequence[len(sequence)-1]:
                i-=1
                break
        #左右子树自己的数组
        left=sequence[:i+1]
        right=sequence[i+1:len(sequence)-1]
        #右子树是否每个值都大于根
        for j in right:
            if j<sequence[-1]:
                return False
        self.VerifySquenceOfBST(left)
        self.VerifySquenceOfBST(right)
        return True


发表于 2020-01-12 20:24:54 回复(0)
Python
黄沙遮天头像 黄沙遮天 
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        root=0
        if len(sequence)!=0:
            root=sequence[-1]
        flag=0
        if len(sequence)>1:
            #判断首个元素和最后一个元素的大小关系
            if sequence[0]<root:
                #首元素小于最后一个元素会有两种情况，一个是全部小于，另一个是一半小于，另一半大于，且小于部分全小于，大于部分全大于
                i=0
                for i in range(0,len(sequence)-1):
                    if sequence[i]>root:
                        flag=1
                        break
                if flag==1:
                    y=i
                    for y in range(i,len(sequence)-1):
                        if sequence[y]<root:
                            flag=0
                            break
                    if y>i and y<len(sequence)-1 and flag==0:
                        return False
                    else:
                        return self.VerifySquenceOfBST(sequence[:y]) and self.VerifySquenceOfBST(sequence[y:-1])
                if flag==0:
                    return self.VerifySquenceOfBST(sequence[:-1])
            elif sequence[0]>root:
                #当首元素大于最后一个元素时，只有全部都大于最后一个元素，才符合二叉搜索树
                flagg=0
                for z in range(0,len(sequence)-1):
                    if sequence[z]<root:
                        flagg=1
                        return False
                if flagg==0:
                    return self.VerifySquenceOfBST(sequence[:-1])
        elif len(sequence)==1:
            #单个元素，返回正确
            return True
        else:
            #空列表不是二叉搜索树
            return False
此题主要是基于二叉搜索树的特点，即左子树的点全都小于根的值，且右子树的点全都大于根的值。
再根据后续遍历的特定，最后一个元素是根，然后通过判断首元素跟根的关系，判断出有三种情况，
首先是首元素小于根元素，且后面的所有元素都小于根元素；然后是首元素小于根元素，且后面有一段连续到根的数据都是大于根；最后是首元素大于根元素，且后面都大于根元素。只有上面这三种情况才
符合二叉搜索树的特定。另外需要注意空列表不是二叉搜索树
发表于 2019-12-11 13:41:24 回复(0)
Python
吕营头像 吕营

python  

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if sequence ==[]:
            return False
        rootNum = sequence[-1]
        del sequence[-1]
        index = None
        for i in range(len(sequence)):
            if index == None and sequence[i] > rootNum:
                index = i 
            if index != None and sequence[i] < rootNum:
                return False
            #else: return True
        if sequence[:index] ==[]:
            return True
        else: 
             leftret = self.VerifySquenceOfBST(sequence[:index])
        if sequence[index:] ==[]:
            return True
        else:
            rightret = self.VerifySquenceOfBST(sequence[index:])
        return leftret and rightret


发表于 2019-12-09 15:43:56 回复(0)
Python
天山剑客头像 天山剑客 
# -*- coding:utf-8 -*-
# 解题思路：数组最后一个元素为根节点，用根节点把前边的元素分为两部分
# 比根小的组成左子树，比根小的组成右子树
# 左子树和右子树也需要满足二叉搜索树后续遍历，使用递归即可
# 边界条件：数组为空返回false,右子树中有元素比根小返回false
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False

        if len(sequence) == 1:
            return True

        root = sequence.pop()
        i = 0
        while i < len(sequence):
            if sequence[i] > root:
                break
            i += 1

        for j in sequence[i:]:
            if j < root:
                return False

        lf = True
        if sequence[0:i]:
            lf = self.VerifySquenceOfBST(sequence[0:i])

        rf = True
        if sequence[i:]:
            rf = self.VerifySquenceOfBST(sequence[i:])

        return lf and rf

发表于 2019-12-06 16:42:38 回复(0)
Python
Kirto先森头像 Kirto先森 
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        #基本思路: 左子树值<根，右子树>根
        #序列为空返回False
        if not sequence:
            return False
        #序列只有一个元素返回True
        n = len(sequence)
        if n==1:
            return True
        root = sequence[n-1]
        #开始找左子树,index最终为右子树的开头
        index = 0
        while index < n-1:
            if sequence[index]>root:
                break
            index += 1
        #判断右子树中是否存在小于root的值
        for i in range(index,n-1):
            if sequence[i] < root:
                return False
        #存在左右子树就遍历
        left = self.VerifySquenceOfBST(sequence[:index]) if index>0 else True
        right = self.VerifySquenceOfBST(sequence[index:-1]) if index<n-1 else True
        return left and right

发表于 2019-11-08 19:45:03 回复(0)
提交观点

问题信息

栈 树
难度：
76条回答 176033浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号