剑指Offer——二叉搜索树的后序遍历序列

By AverageJoeWang
 标签:

二叉搜索树的后序遍历序列

  • 题目描述
    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

  • 解题思路

    • 最后一个是root
    • 数组前半部分是比root小的
    • 数组后半部分是比root大的
  • 代码实现

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int length = sequence.length;
        if (length <= 0)
            return false;
        int root = sequence[length - 1];
        int i = 0;
        while (i < length - 1 && sequence[i++] < root);
        while (i < length - 1 && sequence[i++] > root);
        return i == length - 1;
    }
}