(python)小菜犬アルゴリズム日記(二叉木シリーズ)剣指offer leetcode面接問題33.二叉探索ツリーの後順ループシーケンス

整数配列を入力し、その配列が二叉探索ツリーの後順遍歴結果であるかどうかを判断します.もしそうであればtrueを返し、そうでなければfalseを返します.入力された配列の任意の2つの数字が互いに異なると仮定します.
次のツリーを参照してください.
5/2 6/1 3例1:
入力:[1,6,3,2,5]出力:false例2:
入力:[1,3,2,6,5]出力:true
ヒント:
配列長<=1000
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof二叉探索木と後順遍歴によれば,最後尾は根であり,根より小さいのは左サブツリー,根より大きいのは右サブツリーである.
再帰的終了条件、listは空です.再帰的に繰り返すことでroot=list[-1]に基づいてlistを左サブツリーと右サブツリーに分け、左サブツリーの各要素がrootより小さいかどうか、右サブツリーの各要素がrootより小さいかどうかを判断します.戻り値:左サブツリーand右サブツリーの判断をチェックします.

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if not postorder:
            return True
        root = postorder[-1]
        pos = 0
        for i in postorder[:-1]:
            if i>root:
                break
            pos+=1
        left = postorder[:pos]
        right = postorder[pos:-1]
        # for i in left: #  pos          root        
        #     if i>root:
        #         return False
        for i in right:
            if i

タイトルの説明
整数配列を入力し、その配列が二叉探索ツリーの後順に遍歴した結果であるかどうかを判断します.もしそうであればYesを出力し、そうでなければNoを出力します.入力された配列の任意の2つの数字が互いに異なると仮定します.
剣はOfferの上でこの問題が少し異なっていることを指して、sequence=[]の時、Falseを返して、leetcodeはTrueを返して、だからいくつかの小さい工程が多くなりました

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        if len(sequence)==1:
            return True
        root = sequence[-1]
        pos = 0
        for i in sequence[:-1]:
            if i>root:
                break
            pos+=1
        left = sequence[:pos]
        right = sequence[pos:-1]
        for i in right:
            if i0:
            lefts = self.VerifySquenceOfBST(left)
        if len(right)>0:
            rights = self.VerifySquenceOfBST(right)
        return lefts and rights

2回目に書いた時に使いました.

pos = 0
for i in sequence[:-1]:
    if i>root:
        pos =  sequence.index(i)
        break

エラーを報告して、テストの例を考えてみました.例えば[3,5,7]の根は7で、3,5はすべて左で、この時右の木がなくて、posが見つからなくて、デフォルト値0では適切ではありません.前のpos+=1はこの問題を解決することができます.