Java日常练习题,每天进步一点点(56)

Java日常练习题,每天进步一点点(56) - 完整攻略

题目描述

给定一个数组，判断它是否为某个二叉搜索树的后序遍历结果。

示例输入

int[] postorder = {5, 7, 6, 9, 11, 10, 8};

示例输出

true

解题思路

二叉搜索树（BST）的定义是，对于任意节点 n，它的左子树（如果存在）上所有节点的值都小于等于 n 的值，右子树（如果存在）上所有节点的值都大于等于 n 的值。而二叉搜索树的后序遍历是指，先遍历左子树、再遍历右子树、最后遍历根节点的顺序。因此，对于一个给定的数组，我们需要首先确定它是不是某个二叉搜索树的后序遍历结果。如果是，我们再判断该数组是否构成一颗合法的二叉搜索树。

因为一个合法二叉树的后序遍历顺序，有一个很显然的特点——根节点一定是后序遍历序列的最后一个元素，且它把整个序列分为了左右两个子序列。左子序列的所有元素都比根节点的值小，右子序列的所有节点都比根节点的值大。根据这个特点，我们可以进行以下的求解过程：

• 假设当前序列的长度为 n，最后一个元素为根节点。
• 从前往后找到第一个大于根节点的元素下标 i，这个下标之前的所有元素一定都在根节点的左子树中。
• 继续从下标 i 开始往后遍历，如果发现有小于根节点的元素，则说明该序列不能构成一个合法的二叉搜索树。
• 否则，分别对左右子序列进行递归处理，如果都是合法的二叉搜索树，则该序列也是一棵合法的二叉搜索树。

解题代码

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

    private boolean verify(int[] sequence, int start, int end) {
        // 只剩一个结点或没有结点时，都视为有效的二叉搜索树
        if (start >= end) {
            return true;
        }
        int rootValue = sequence[end];  // 后序遍历序列的最后一个结点为根结点
        int i = start;
        // 找到左、右子树的分界点
        while (i < end && sequence[i] < rootValue) {
            i++;
        }
        // 判断右子树的值是否都大于根结点的值
        for (int j = i; j < end; j++) {
            if (sequence[j] < rootValue) {
                return false;
            }
        }
        // 递归判断左右子树是否是二叉搜索树
        return verify(sequence, start, i - 1) && verify(sequence, i, end - 1);
    }

解题说明

在本题中，我们先将给定的数组序列分为左右两个子序列，其中左子序列的所有元素都比根节点的值小，右子序列的所有元素都比根节点的值大。然后，我们再递归地对左右子序列进行判断，验证它们是否都是合法的二叉搜索树。

我们需要注意，对于二叉搜索树而言，存在若干个符合条件的节点分布方式。因此，从遍历结果出发理解二叉搜索树并不容易。因此，我们需要从二叉搜索树的定义出发，从节点的值域大小关系上推，这是理解本题的关键。