边工作边刷题：70天一遍leetcode: day 84-1

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])