本文主要是介绍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:的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!