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)

           

處理一顆二叉樹的周遊序列時，可以先找到二叉樹的根節點