[Leetcode] Verify Preorder Sequence in Binary Search Tree

Problem:
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.

我的第一个想法有点类似于quick sort，数组的第一个元素，必然是BST的root，那么我现在只需要去找下一个比这个root大的元素，假设其index为i，那么从1到i-1的元素应该是BST的left subtree，而i以后的元素是right subtree。但是如果i以后的元素有比root还要小的，那么这个preorder的数组必然不是from BST。

This is very similar to quick sort procedure. Therefore, the time complexity on average is O(n log n), too slow for this problem. My code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution(object): def verifyPreorder(self, preorder): """ :type preorder: List[int] :rtype: bool """ if not preorder or len(preorder) == 1: return True first = preorder[0] for i in xrange(1, len(preorder)): if preorder[i] > first: break if i != len(preorder)-1: for j in range(i, len(preorder)): if preorder[j] < first: return False if preorder[i] > first: left = self.verifyPreorder(preorder[1:i]) if not left: return False right = self.verifyPreorder(preorder[i:]) return right elif preorder[i] < first: left = self.verifyPreorder(preorder[1:i+1]) return left

很明显，我们重复看了很多的子问题，比如the first half, we later have to re-look at it in solving self.verifyPreorder(preorder[1:i])