【剑指报价】二叉搜索树（Python）后遍历序列问题解决报告

主题地址:

输入一个整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

我们都知道BST的中间顺序遍历是有序的，而后顺序遍历时，最后一个节点是根节点. 然后，您可以先找到根节点，然后使用根节点的值将数组分为两部分. 前部小于根节点是左子树，后部大于根节点是右子树. 然后分别遍历左右子树. 当我解决此问题时序列二叉排序树，我使用了从左到左的遍历来查找比根节点大的第一个位置，以划分左节点和右节点. 这样可以确保左侧部分小于根节点，并且不能保证右侧部分大于根节点. 部分验证. 另外序列二叉排序树，标题中有一个坑. 标题认为空树不是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)

2018年3月20日-就在阳光下，安心学习

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-236094-1.html