剣指offer二叉探索木の後序遍歴シーケンスpython

タイトルの説明
整数配列を入力し、その配列が二叉探索ツリーの後順に遍歴した結果であるかどうかを判断します.もしそうであればYesを出力し、そうでなければNoを出力します.入力された配列の任意の2つの数字が互いに異なると仮定します.
サンプル

[1,2,3,4,5] 
true
[1,2,3,6,4,5]
false

アイデア1:再帰メソッドを使用して、最後の要素、すなわちrootを取り出すたびに、すべてのノードを巡り、左サブツリーと右サブツリーを見つけ、それぞれこのメソッドを使用して検索します.

class Solution:
    def VerifySquenceOfBST(self, sequence):
        if sequence == []:
            return False
        if len(sequence) == 1 or len(sequence) == 2:
            return True
        else:
            root = sequence.pop(-1)
            sign = 0
            note = 0
            flag = 0
            for i in range(len(sequence)):
                if sign is 0 and sequence[i] > root:
                    note = i
                    sign = -1
                if sequence[i] > root:
                    sign = 1
                    flag += 1
                if (sign == 1) and (sequence[i] < root):
                    return False
            if sign is 0:
                note = i
            if flag == len(sequence):
                note = 1
            return self.VerifySquenceOfBST(sequence[:note]) and self.VerifySquenceOfBST(sequence[note:])

考え方2:討論区は似たような解法を見て、左右のサブツリーを判断しないで、直接脳の再帰シーケンスがなくて、もし不法なシーケンスが現れたら、つまり右のサブツリーの中でrootより小さくて、falseに戻って、その他の情況の直接シーケンスは1つ減らして再帰を続けます.

class Solution:
    def VerifySquenceOfBST(self, sequence):
        if sequence == []:
            return False
        if len(sequence) == 1 or len(sequence) == 2:
            return True
        else:
            root = sequence.pop(-1)
            sign = 0
            for i in range(len(sequence)):
                if sequence[i] > root:
                    sign = 1
                if (sign == 1) and (sequence[i] < root):
                    return False
            return self.VerifySquenceOfBST(sequence[:i]) and self.VerifySquenceOfBST(sequence[i:])

最後に
ブラシしたLeetCodeや剣指offerのソースコードをGithubに置いて、好きな友达や役に立つと思う友达にstarやfollowを注文してほしいです.以下のコメントや私信や連絡先で私を探すことができます.連絡先QQ:791034063 Wechat:liuyuhang 791034063 CSDN:https://blog.csdn.net/Sun_White_Boy Github:https://github.com/liuyuhang791034063
転載先:https://www.cnblogs.com/GF66/p/9785464.html