题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0) {
return false;
}
return verify(sequence, 0, sequence.length - 1);
}
private boolean verify(int[] arr, int first, int last) {
if(last - first <= 1) {
return true;
}
int rootVal = arr[last];
int riFirst = first;
for(; riFirst < last; riFirst++) {
if(arr[riFirst] > rootVal) {
break;
}
}
for(int i = riFirst + 1; i < last; i++) {
if(arr[i] < rootVal) {
return false;
}
}
return verify(arr, first, riFirst - 1) && verify(arr, riFirst, last - 1);
}
}
