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

成都創新互聯公司專業為企業提供涇源網站建設、涇源做網站、涇源網站設計、涇源網站制作等企業網站建設、網頁設計與制作、涇源企業網站模板建站服務，10年涇源做網站經驗，不只是建網站，更提供有價值的思路和整體網絡服務。

class Solution:
    """
    一個二叉搜索樹BST滿足： max(左子樹) < 根節點 < min(右子樹)
    由于題目給出的是一個后序遍歷，那么序列的最后一個元素就應該是根節點。
    因此我們從BST的定義出發，遍歷整個序列，找到第一個大于根節點的元素k，k以前的元素屬于左子樹，
    從k開始到根節點之前的元素屬于右子樹。
    如果遍歷整個序列之后得到的左右子樹都滿足BST的定義，則遞歸判斷左子樹和右子樹是否滿足BST定義
    """
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False

        root = sequence[-1]  # 獲取根節點
        """
        查找第一個大于根節點的元素，得到左右子樹的分界點
        """
        idx = 0
        while idx < len(sequence) - 1:
            if sequence[idx] > root:
                break
            idx += 1

        # 需要驗證右子樹是否滿足BST，即所有右子樹的節點都大于根節點，
        # 如果不滿足則這個序列不是BST的后序遍歷
        for i in range(idx, len(sequence) - 1):
            if sequence[i] < root:
                return False

        # 如果這個序列是BST的后序遍歷，那么遞歸判斷左右子樹是否分別滿足BST
        left = True
        if idx > 0:
            left = self.VerifySquenceOfBST(sequence[: idx])

        right = True
        if idx < len(sequence) - 1:
            right = self.VerifySquenceOfBST(sequence[idx: -1])

        return left and right

另外有需要云服務器可以了解下創新互聯cdcxhl.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

新聞名稱：劍指offer：二叉搜索樹的后序遍歷序列-創新互聯
分享地址：http://vcdvsql.cn/article44/dspphe.html

成都網站建設公司_創新互聯，為您提供自適應網站、做網站、ChatGPT、移動網站建設、網站內鏈、動態網站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯