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

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

后序遍历得到的序列，最后一个值为根节点的值，数组中前面的数字分为两部分第一部分是左子树节点的值，他们都比根节点的值小，第二部分是右子树节点的值，他们都比根节点的值大

错误记录

1. 当需要判断一个范围内数字与某个数字的大小情况时，先判断这个范围是否为空

class Solution:
    def dfs(self, arr, start, end):
        if start >= end:
            return True
        root = arr[end]
        big_than_idx = end
        for i in range(start, end):
            if arr[i] > root:
                big_than_idx = i
                break
        if arr[big_than_idx:end] and min(arr[big_than_idx:end]) < root:
            return False
        return self.dfs(arr,start, big_than_idx-1) and self.dfs(arr, big_than_idx, end-1)
        
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False
        root = sequence[-1]
        big_than_idx = len(sequence)-1
        for i in range(len(sequence)):
            if sequence[i] > root:
                big_than_idx = i
                break
        if sequence[big_than_idx:-1] and min(sequence[big_than_idx:-1]) < root:
            return False
        return self.dfs(sequence,0,big_than_idx-1) and self.dfs(sequence, big_than_idx, len(sequence)-2)

           

处理一颗二叉树的遍历序列时，可以先找到二叉树的根节点