LeetCode 题解(264) : Verify Preorder Sequence in Binary Search Tree：

本文主要是介绍LeetCode 题解(264) : Verify Preorder Sequence in Binary Search Tree：，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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?

题解：

不用constant space的解法反而比较难想。用一个stack模拟preorder traverse的过程。每push当前元素时，需要与一个表示当前根的值的变量比较，如果小于当前根，那么无法满足preorder traverse。否则，如果stack不为空，且stack里有小于当前元素的元素，pop只到不小为止，同时更新low为最后一个pop出的小于当前元素的值（其实是加入当前元素后的根的值）。最后把当前元素加入stack。

class Solution(object):def verifyPreorder(self, preorder):low = -sys.maxints = []for i in preorder:if i < low:return Falsewhile len(s) != 0 and s[-1] < i:low = s.pop()s.append(i)return True

用递归可以实现constant space，思路比较直接，但是时间复杂度较高，无法通过时间测试。

class Solution {
public:bool verifyPreorder(vector<int>& preorder) {if(preorder.size() <= 1)return true;return verify(preorder, 0, preorder.size() - 1);}bool verify(vector<int>& preorder, int start, int end) {if(start >= end)return true;int i = start + 1;while(preorder[i] < preorder[start])i++;for(int j = i; j <= end; j++)if(preorder[j] < preorder[start])return false;return verify(preorder, start + 1, i - 1) && verify(preorder, i, end);}
};

这篇关于LeetCode 题解(264) : Verify Preorder Sequence in Binary Search Tree：的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---