【剣指Offer】二叉探索木の後序遍歴シーケンス解題報告(Python)

【剣指Offer】二叉探索木の後序遍歴シーケンス解題報告(Python)
ラベル(スペース区切り):剣指Offer
タイトルアドレス:https://www.nowcoder.com/ta/coding-interviews
タイトルの説明:
整数配列を入力し、その配列が二叉探索ツリーの後順に遍歴した結果であるかどうかを判断します.もしそうであればYesを出力し、そうでなければNoを出力します.入力された配列の任意の2つの数字が互いに異なると仮定します.
解題方法
BSTの中順序遍歴は秩序化され,後順序遍歴,最後のノードはルートノードであることを知っている.では、まずルートノードを探して、ルートノードの値を利用して、配列を2つの部分に分けて、前の部分はルートノードより小さくて左のサブツリーで、後ろの部分はルートノードより大きくて右のサブツリーです.それからそれぞれ左右の子木を遍歴すればいいです.私はこの問題をするときに左遍歴から最初のルートノードより大きい位置を見つけて左右のノードを区分し,左の部分がルートノードより小さいことを保証し,右の部分がルートノードより大きいことを保証できないので,右の部分を検証した.また,問題にはピットがあり,空木はBSTではないと考えられているため,関数を新たに定義して再帰しないと,より簡単になる.

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, nums):
        if not nums: return False
        return self.verifyBST(nums)

    def verifyBST(self, nums):
        if not nums: return True
        root = nums.pop()
        index = self.findIndex(nums, root)
        if self.verifyRight(nums[index:], root):
            left = nums[:index]
            right = nums[index:]
            return self.verifyBST(left) and self.verifyBST(right)
        return False

    def verifyRight(self, nums, target):
        if not nums: return True
        return min(nums) > target

    def findIndex(self, nums, target):
        for i, num in enumerate(nums):
            if num > target:
                return i
        return len(nums)

Date
2018年3月20日–日差しがちょうど良く、安心して勉強