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.
public class Solution {
public boolean verifyPreorder(int[] preorder) {
return helper(preorder, 0, preorder.length - 1);
}
public boolean helper(int[] preorder, int left, int right) {
if (left >= right) {
return true;
}
int i = left + 1;
while (i <= right && preorder[i] < preorder[left]) {
i++;
}
int j = i;
while (j <= right) {
if (preorder[j] > preorder[left]) {
j++;
} else {
return false;
}
}
return helper(preorder, left + 1, i - 1) && helper(preorder, i, right);
}
}
没有评论:
发表评论