剑指offer最优解Java版-二叉搜索树的后序遍历序列
2019-06-25 本文已影响1人
全菜工程师小辉
题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出true,否则输出false。假设输入的数组的任意两个数字都互不相同。
解决方法
根据后序遍历特点,数值由小到大再变小,来进行检验。
public class Solution {
public boolean VerifySquenceOfBST(int[] sequence) {
int size = sequence.length;
if (0 == size) return false;
int i = 0;
while (--size > 0) {
while (sequence[i++] < sequence[size] && i < size) ;
while (sequence[i++] > sequence[size] && i < size) ;
if (i < size) return false;
i = 0;
}
return true;
}
}
复杂度分析:
- 时间复杂度:O(n)。
- 空间复杂度:O(1)。