Verify preorder sequence of Binary Search Tree

要点：simulating preorder sequence：

• 根据preorder的特点，首先会一直向left subtree方向访问，并且值递减。当遇到一个非递减元素是，说明这个是某个当前路径上结点作为根的right subtree上的点。
• 首先我们要找到这个根结点：如果之前把所有元素都存到stack里，stack按pop顺序是从小到大的，不断pop，最后一个小于当前元素的结点即为root（记法：因为不断更新low，所以root.val最终在low里）。另外xstack[-1]就停了，也就是把作为right subtree处理。
• invalid：pop出来的以后，序列都要更大：因为不断向右子树方向走（parent的root已经访问过），low是不断变大的。下一个low可能往父节点走，也可能继续右子树。之后的结点必须大于low，否则invalid

https://repl.it/CfR8/1

错误点：注意[9,5,7,8]这是valid的，如果把8放在root 9右边当然不符合，但是也可以放到7右边，preorder并不是唯一的。

recursion approach

• based on: preorder序列的第一个点把值域分割：所以很容易adapt到top-down approach
• recursion：每层loop：根据中点値找到left/right tree的交接点：这样可以recurse到left/right subtree
  • loop中验证subtree的值不能超过上层pass下来的区间
  • redundant: loop中的验证重复进行多次

https://tonycao.gitbooks.io/leetcode-locked/content/LeetCode Locked/c1.14.html

O(1): 要点是重用当前sequence：因为stack的size不会超过当前遍历的元素。用global i来记录stack top的位置即可，所以用sequence的[0，i]来存stack。

错误点：注意i表示当前栈顶，那么初始化为-1。

https://repl.it/Cf1t

# 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?

# Hide Company Tags Zenefits

# Hide Tags Tree Stack

# Hide Similar Problems (M) Binary Tree Preorder Traversal

class Solution(object):

    def verifyPreorder(self, preorder):

        """

        :type preorder: List[int]

        :rtype: bool

        """

        low = -sys.maxint

        stk = []

        for p in preorder:

            if p<low:

                return False

            while stk and p>stk[-1]:

                low = stk.pop()

            stk.append(p)

        return True

import sys

class Solution:

    # @param {integer[]} preorder

    # @return {boolean}

    def verifyPreorder(self, preorder):

    	low = -sys.maxint

    	i = -1

    	for x in preorder:

    		if x < low:

    			return False

    		while i>=0 and x>preorder[i]:

    			low = preorder[i]

    			i-=1

    		i+=1

    		preorder[i]=x

    	return True

sol = Solution()

print sol.verifyPreorder([2, 4, 1])

print sol.verifyPreorder([40, 30, 35, 80, 100])

print sol.verifyPreorder([40, 30, 35, 20, 80, 100])