Verify Preorder Sequence of Binary Search Tree

题目描述

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:

Could you do it using only constant space complexity?

解题方法

preorder的特点是，自身，左子树，右子树，所以visit了一个点之后，直到遇到一个更大的 value,之间的都应该是左子树的，后面的都是右子树的。

而不valid的情况就是在右子树中遇到了小于root.val的值。

  1. 递归

递归的方法就是按照上面的思想，找到左右子树的分界点，然后递归判断 退出条件就是右子树有小于root的值。例code

  1. stack

stack保存左子树的值，直到遇到一个升序的数字，而右子树的值都应该大于当前root的value, 所以我们应该将这个value保存下来，用来判断是否是valid的BST.

  1. constant space

当一个array的问题，我们又不是使用额外的space,那么很自然地就应该想我们应该使用 本来array的space.那么这一题应该怎样使用呢？

因为我们是从前往后Loop, 而且前面访问过的不会再访问了，所以前面的空间我们可以 当做stack，并且用一个Pointer来代替stack的pop, append移动

Solution

stack

class Solution(object):
    def verifyPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: bool
        """
        if not preorder:
            return True

        stack = []
        lower_limit = -sys.maxint

        for val in preorder:
            if val < lower_limit: # 判断条件
                return False
            while stack and val > stack[-1]: 
                # 到右子树了，一直pop到右子树的parent, 这个parent是右子树的lower limit
                lower_limit = stack.pop()
            stack.append(val)

        return True

Reference