算法:二叉搜索树的后序遍历序列

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

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

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。

假设输入的数组的任意两个数字都互不相同。

分析

由于是二叉搜索树, 而且是后序遍历, 所以一定有:

• arr[end]就是当前子树的根节点

• 左子树arr[i] < arr[end]

• 右子树arr[i] > arr[end]

  所以类似于快排, 对于二叉树的子树进行递归, 并拆分左右子树, 判断上面的规则;

代码

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) return false;
        return isBST(sequence, 0, sequence.length - 1);
    }

    private boolean isBST(int[] arr, int start, int end) {
        // 问题边界
        if (end <= start) return true;
        // end为当前树的根, pivot为BST的左右分隔节点;
        int pivot = start;
        // 左侧都小于arr[end]
        for (; pivot < end; ++pivot) {
            if (arr[pivot] > arr[end]) break;
        }
        // 右侧都大于arr[end]
        for (int j = pivot; j < end; ++j) {
            if (arr[j] < arr[end]) return false;
        }
        return isBST(arr, start, pivot - 1) && isBST(arr, pivot, end - 1);
    }
}