[LeetCode]Verify Preorder Sequence in Binary Search Tree

给定Preorder序列，如果是valid的话，构造出来的BST应该是唯一的。那么什么样的input是不valid的呢？首先我们肯定递增序列是不会有问题的，因为我们可以一直构建右子节点来满足条件，比如1,2,3,4,5的序列，就是从1开始一直去右子节点到5。换句话说，对于input number来说，没有右边界，输入多大的数都是合理的。那么问题就出在递减序列，也就是说对于某些数来说，是有左边界的。具体来讲，如果出现递减序列，说明进入了当前节点c的左子节点left，如果当前节点是某个节点n的右子树，那么left的值必须大于n的值，也就是说，碰到这种情况的时候我们才能断定，当前preorder序列是不合理的。
具体到算法，我们如何实现呢? 我们做Preorder Traversal即可，注意更新当前的左边界。时间复杂度O(n)，空间复杂度O(log n)，代码如下：



这道题还可以用Divide and Conquer来做，因为我们知道当前区间是一个tree，并且第一个数是root，那么我们可以在O(n)的时间里做二分，找到哪一半是左子树，哪一半是右子树。找到之后，我们继续递归地判断子树是不是valid的即可。
时间复杂度分析T = 2 * T / 2 + n，那么对于每一层递归来说耗时分别为n, n / 2 * 2, n / 4 * 4，总共有log n层，我们可以得到T = n * log n，所以时间复杂度为O(n * log n)，空间复杂度为O(log n)。代码如下：