剑指offer最优解Java版算法todo

剑指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;
    }
}

复杂度分析:

哎呀,如果我的名片丢了。微信搜索“全菜工程师小辉”,依然可以找到我
上一篇下一篇

猜你喜欢

热点阅读