My code:
public class Solution {
public boolean verifyPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) {
return true;
}
return check(preorder, 0, preorder.length - 1);
}
private boolean check(int[] preorder, int begin, int end) {
if (begin >= end) {
return true;
}
int i = begin + 1;
while (i <= end) {
if (preorder[i] < preorder[begin]) {
i++;
}
else {
break;
}
}
int j = i - 1;
while (i <= end) {
if (preorder[i] < preorder[begin]) {
return false;
}
else {
i++;
}
}
return check(preorder, begin + 1, j) && check(preorder, j + 1, end);
}
}
我自己写了出来，但发现很慢。
采用的是 dfs的思想，
发现preorder 一定可以分成三块：
头结点，之后一块总比他小，紧接着一块，总比他大。
所以我先检查这个特征是否满足。
如果满足，再分别检查第二块和第三块是否满足要求，其实就是检查左子树右子树，是否满足要求。
然后看了答案，发现有更加快的做法。
My code:
public class Solution {
public boolean verifyPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) {
return true;
}
Stack<Integer> st = new Stack<Integer>();
int pre = Integer.MIN_VALUE;
for (int i = 0; i < preorder.length; i++) {
if (preorder[i] < pre) {
return false;
}
else {
while (!st.isEmpty() && preorder[i] > st.peek()) {
pre = st.pop();
}
st.push(preorder[i]);
}
}
return true;
}
}
reference:
https://discuss.leetcode.com/topic/21217/java-o-n-and-o-1-extra-space
time: O(n)
space: O(n)
这个利用的原理差不多。但是效率更高。
preorder总是先把左边一条线访问，所以他们的特点是从大变小。
如果突然碰到一个比栈顶更大的数，说明跳到了上一层结点的右孩子了。
那么就可以把比他小的结点都弹出去，然后更新low为自己的值。
如果碰到值比自己小的，说明来来错地方了。
这道题目的意思是什么：
记住，遍历的一定是 valid bst，我们要做的是，preorder this valid BST, -> array, 我们坚持这个array是否是我们预计的。
当然，还可以把栈去了，用原数组充当栈，但我感觉没必要。
Anyway, Good luck, Richardo! -- 09/06/2016
