[数据结构与算法]二叉搜索树的后序遍历序列 -- java

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。

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

例如输入数组 {5，7，6，9，11，10，8} ，则返回true，因为这个整数序列是下图二叉搜索树的后序遍历结果。

如果输入的数组是 {7，4，6，5}，由于没有哪棵二叉搜索树的后序遍历结果是这个序列，因此返回false。

解题思路

• 先找到数组最后一个数字（根节点的值），然后就可以将数组分成两部分：第一部分是左子树，它们都比根节点的值小；第二部分是右子树，它们都比根节点的值大

• 然后就是递归验证左右子树合法（满足二叉搜索树的条件）即可

代码

public class VerifySequenceOfBST {
    public static boolean verifySequenceOfBSE(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }

        return verifySequenceOfBSE(sequence, 0, sequence.length-1);
    }

    /**
     * 核心
     * @param sequence 待判定的数字序列
     * @param start 起始索引
     * @param end 结束索引
     * @return 是不是某二叉搜索树的后序遍历结果
     */
    public static boolean verifySequenceOfBSE(int[] sequence, int start, int end) {

        int root = sequence[end];

        // 在二叉搜索树中左子树节点的值小于根节点的值
        int i = start;
        while (i < end && sequence[i] < root) {
            i++;
        }

        // 在二叉搜索树中右子树节点的值大于根节点的值
        int j = i;
        while (j < end) {
            // 如果右子树小于根节点
            // 那么这个序列就不是二叉树的后序遍历结果
            if (sequence[j] < root) {
                return false;
            }
            j++;
        }

        // 判断左子树是不是二叉搜索树
        boolean left = true;
        if (i > 0) {
            left = verifySequenceOfBSE(sequence, 0, i-1);
        }

        // 判断右子树是不是二叉搜索树
        boolean right = true;
        if (i < end) {
            right = verifySequenceOfBSE(sequence, i, end - 1);
        }

        return (left && right);
    }

    // 测试
    public static void main(String[] args) {
        int[] sequence = {5,7,6,9,11,10,8};
        System.out.println(verifySequenceOfBSE(sequence)); // true

        int[] sequence1 = {7,4,6,5};
        System.out.println(verifySequenceOfBSE(sequence1)); // false

        int[] sequence2 = {2,1};
        System.out.println(verifySequenceOfBSE(sequence2)); // true

        int[] sequence3 = {2};
        System.out.println(verifySequenceOfBSE(sequence3)); // true

    }
}

补充

1. 二叉搜索树
   若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

2. 举一反三
   如果面试题要求处理一棵二叉树的遍历序列，则可以找到二叉树的根节点，再基于根节点把整棵树的遍历序列拆分成左子序列和右子序列，接下来再递归地处理这两个子序列。

来自：

《剑指Offer》
Coding-Interviews/二叉搜索树的后序遍历序列.md at master · todorex/Coding-Interviews