首页 > 试题广场 >

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

[编程题]二叉搜索树的后序遍历序列

热度指数：876927 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

数据范围：节点数量 $0 \le n \le 1000$ ，节点上的值满足 $1 \le val \le 10^{5}$ ，保证节点上的值各不相同
要求：空间复杂度 $O(n)$ ，时间时间复杂度 $O(n^2)$

提示：

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)

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

一.后续遍历的特点 :左->右->跟

二.二叉搜索树的特点 :左子树小于跟小于右子树

三.设计到树通常是一组最简单的单元判断,然后递归子节点

四.空子树不是二叉搜索树,没有子节点的树判断为二叉搜索树

# -*- 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号

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

搜索二叉树，排序二叉树，后序遍历左右根。

只需要考虑一个问题，就是出现大于根的数之后，不能再出现任何一个小于该根的数。

# -*- 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

# -*- 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

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号

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

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号

# -*- 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号

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先森

# -*- 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条回答 4110收藏 177660浏览

通过挑战的用户

查看代码

cramin

2023-03-09 11:49:48
Elastic...

2023-02-26 22:24:20
牛客74843...

2022-10-16 13:51:53
想成为大佬的小菜鸡

2022-09-16 15:19:39
95年的巨蟹

2022-09-16 11:16:37

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

输入

输出

说明

输入

输出

说明

输入

输出

Python Solution

python

问题信息

热门推荐

通过挑战的用户

相关试题