《劍指offer》17：二叉搜索樹的后序遍歷-有解無憂

題目描述

輸入一個整數陣列，判斷該陣列是不是某二叉搜索樹的后序遍歷的結果，如果是則回傳true,否則回傳false，假設輸入的陣列的任意兩個數字都互不相同，

解題思路：

我們隨便構造一個二叉搜索樹，看看有什么規律，假設我們構造了如下圖所示這樣的二叉樹，則有：

那么我們后序遍歷的結果則是：[ 1,4,2,6,11,9,5]，我們可以看到最后一個數字就是這顆樹的根部，同樣的，由于具有二叉搜索樹的特點，右邊的子節點的數值一定比左邊的更大，左邊的數值則一定比右邊的更小，因此可得[1,4,2]是我們左樹遍歷的結果，[6,9,11]是右樹遍歷的結果，我們只要在這個給定的陣列當中找到了一個數值比最后一個數值更大，那么我們就找到了右子樹，再用遞回分別對左子樹和右子樹進行遞回即可，因此這道題最重要的就是需要尋找到第一個需要比最后一個數字更大的那個數值的索引，代碼如下：

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False

        root = sequence[-1]
        # 根據二叉搜索樹的性質，左孩子的每個結點的值都小于根節點,這個i并不會因回圈的消失而消失,i代表陣列當中的索引，我們人為做的是第一次簡要的遞回判斷
        for i in range(len(sequence)):
            if sequence[i] > root:
                break
        # 判斷是否右孩子的每個結點的值都大于根結點
        for j in range(i, len(sequence)):
            if sequence[j] < root:
                return False
        left = True
        # 遞回開始，i > 0 的時候證明有左孩子，i<0就證明沒有，說明左樹已經遍歷完畢
        if i > 0:
            # 遞回遍歷左孩子
            left = self.VerifySquenceOfBST(sequence[ : i])
        right = True
        # 證明有右孩子，通過i的值不在最后一個結點判斷，len(sequence) - 1 為sequence的最后一個結點.如果i已經在最后一個節點了，則不進行判斷
        if i < len(sequence) - 1:
            right = self.VerifySquenceOfBST(sequence[i : -1])
        return left and right

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143967.html

標籤：其他

上一篇：0763. Partition Labels (M)

下一篇：詳細分析堆疊和佇列的資料結構的實作程序（Java 實作）