255 Verify Preorder Sequence in Binary Search Tree
255. Verify Preorder Sequence in Binary Search Tree
题目: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
难度:
Medium
思路：
这道题让给了我们一个一维数组，让我们验证其是否为一个二叉搜索树的先序遍历出的顺序，我们都知道二叉搜索树的性质是左<根<右，如果用中序遍历得到的结果就是有序数组，而先序遍历的结果就不是有序数组了，但是难道一点规律都没有了吗，其实规律还是有的，根据二叉搜索树的性质，当前节点的值一定大于其左子树中任何一个节点值，而且其右子树中的任何一个节点值都不能小于当前节点值，那么我们可以用这个性质来验证，举个例子，比如下面这棵二叉搜索树：
10
/ \
5 12
/ \
2 6
preorder:[10, 5, 2, 6, 12]
如这个例子，我们先设一个最小值min_num，然后遍历数组，如果当前值小于这个最小值min_num，返回false，对于根节点，我们将其压入栈中，然后往后遍历，如果遇到的数字比栈顶元素小，说明是其左子树的点，继续压入栈中，直到遇到的数字比栈顶元素大，那么就是右边的值了，我们需要找到是哪个节点的右子树，所以我们更新low值并删掉栈顶元素，然后继续和下一个栈顶元素比较，如果还是大于，则继续更新low值和删掉栈顶，直到栈为空或者当前栈顶元素大于当前值停止，压入当前值，这样如果遍历完整个数组之前都没有返回false的话，最后返回true即可
O(n) time, O(n) space
class Solution(object):
def verifyPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: bool
"""
stack = []
min_num = -1 << 31 # 初始化最小值为最小整数
for x in preorder:
if x < min_num: # 违反最小值限定则是无效的
return False
while stack and x > stack[-1]: # 将路径中所有小于当前的数pop出来并更新最小值
min_num = stack.pop()
stack.append(x) # 将当前值push进去
return True
Follow up:
O(n) time, O(1) space
we realize that the preorder array can be reused as the stack thus achieve O(1) extra space, since the scanned items of preorder array is always more than or equal to the length of the stack.
class Solution(object):
def verifyPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: bool
"""
# stack = preorder[:i], reuse preorder as stack
min_num = -1 << 31
i = 0
for x in preorder:
if x < min_num:
return False
while i > 0 and x > preorder[i - 1]:
min_num = preorder[i - 1]
i -= 1
preorder[i] = x
i += 1
return True
