劍指offer 二叉搜尋樹的後序周遊序列 python

題目描述

輸入一個整數數組，判斷該數組是不是某二叉搜尋樹的後序周遊的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。

樣例

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

想法一：

使用遞歸方法，每次取出最後一個元素，即為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:])
                

想法二：

讨論區看到了相似的解法，不通過判斷左右子樹，直接無腦遞歸序列，如果出現了不合法序列，即右子樹中小于root，傳回false，其他情況直接序列減一繼續遞歸。

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：liuyuhang791034063

CSDN：https://blog.csdn.net/Sun_White_Boy

Github：https://github.com/liuyuhang791034063

轉載于:https://www.cnblogs.com/GF66/p/9785464.html