題目描述
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, s):
        # write code here
        def VerifySquenceOfBST2(s):
            if not s: return True
            i = 0
            while s[i]<s[-1]: i+=1
            for j in range(i,len(s)):
                if s[j]<s[-1]: return False
            return VerifySquenceOfBST2(s[:i]) and VerifySquenceOfBST2(s[i:-1])
        
        if not s: return False
        return VerifySquenceOfBST2(s)