255. Verify Preorder Sequence in Binary Search Tree

"""
Grandyang
http://www.cnblogs.com/grandyang/p/5327635.html
"""

import sys

class Solution(object):
    def verifyPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: bool
        """
        low = -sys.maxsize # low 其实是bst中的root节点，也就是说left < root < right

        st = []

        for val in preorder:
            if val < low:   # 如果当前的val < low 说明右子树的值小于root. 返回False
                return False

            # 这一步是在找当前val是的root节点是那个值，如果val > stack.top 就把当前top的值更新到low中，此时low里面的值是val的可能的root节点。
            # 直到val < st[-1]，则说明val在top值的左子树，那么上一个更新的low的值就是val的root节点。
            # 如果stack为空，怎说明val是根节点的右子树，此时low为根节点
            while st and val > st[-1]:
                low = st.pop()

            # 将根节点一次压入stack，为了之后寻找。
            st.append(val)

        return True