劍指Offer（二十三）：二叉搜索樹的后序遍歷序列

搜索微信公眾號(hào):'AI-ming3526'或者'計(jì)算機(jī)視覺這件小事' 獲取更多算法、機(jī)器學(xué)習(xí)干貨
csdn：https://blog.csdn.net/baidu_31657889/
github：https://github.com/aimi-cn/AILearners

一、引子

這個(gè)系列是我在?？途W(wǎng)上刷《劍指Offer》的刷題筆記，旨在提升下自己的算法能力。
查看完整的劍指Offer算法題解析請(qǐng)點(diǎn)擊：劍指Offer完整習(xí)題解析

二、題目

輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。

1、思路

首先我們要清楚后序遍歷的概念。遍歷的最后一個(gè)數(shù)字是根節(jié)點(diǎn)，左子樹的值都是小于根節(jié)點(diǎn)的，右子樹的值都是大于根節(jié)點(diǎn)。

舉個(gè)例子：

file

以{5,7,6,9,11,10,8}為例，后序遍歷結(jié)果的最后一個(gè)數(shù)字8就是根結(jié)點(diǎn)的值。在這個(gè)數(shù)組中，前3個(gè)數(shù)字5、7和6都比8小，是值為8的結(jié)點(diǎn)的左子樹結(jié)點(diǎn)；后3個(gè)數(shù)字9、11和10都比8大，是值為8的結(jié)點(diǎn)的右子樹結(jié)點(diǎn)。

我們接下來(lái)用同樣的方法確定與數(shù)組每一部分對(duì)應(yīng)的子樹的結(jié)構(gòu)。這其實(shí)就是一個(gè)遞歸的過(guò)程。對(duì)于序列5、7、6，最后一個(gè)數(shù)字6是左子樹的根結(jié)點(diǎn)的值。數(shù)字5比6小，是值為6的結(jié)點(diǎn)的左子結(jié)點(diǎn)，而7則是它的右子結(jié)點(diǎn)。同樣，在序列9、11、10中，最后一個(gè)數(shù)字10是右子樹的根結(jié)點(diǎn)，數(shù)字9比10小，是值為10的結(jié)點(diǎn)的左子結(jié)點(diǎn)，而11則是它的右子結(jié)點(diǎn)。

我們使用遞歸的方法，先判斷數(shù)組的左子樹和右子樹的位置，然后再判斷左子樹、右子樹是不是二叉搜索樹。

2、編程實(shí)現(xiàn)

python

代碼實(shí)現(xiàn)方案：

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not len(sequence):
            return False
        if len(sequence) == 1:
            return True
        # 定義整個(gè)數(shù)的長(zhǎng)度
        length = len(sequence)
        # 根節(jié)點(diǎn)的值
        root = sequence[-1]
        i = 0
        # 判斷左子樹的位置
        while sequence[i] < root:
            i = i+1
        k = i
        # 判斷右子樹的值是否都大于根節(jié)點(diǎn)root
        for j in range(i,length-1):
            if sequence[j] < root:
                return False
        left_s = sequence[:k]
        right_s = sequence[k:length-1]
        left , right = True, True
        # 遞歸遍歷左右子樹的值
        if len(left_s) > 0:
            left = self.VerifySquenceOfBST(left_s)
        if len(right_s) > 0:
            right = self.VerifySquenceOfBST(right_s)
        return left and right

AIMI-CN AI學(xué)習(xí)交流群【1015286623】 獲取更多AI資料

分享技術(shù)，樂(lè)享生活：我們的公眾號(hào)計(jì)算機(jī)視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關(guān)注！