【二叉树冲头1】二叉树的后遍历序列

输入一个整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果是二叉排序树中序遍历，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

中

通常，大多数二叉树问题都可以使用递归来解决. 这个问题也是递归的. 这个想法如下:

二进制搜索树的以下序列具有这样的特征: 序列的最后一个值是二进制树的根；二叉搜索树的左子树值小于根，右子树值大于根.

所以我们可以这样做:

1. 确保找到根；

2. 遍历序列（不包括根节点）以找到大于根的第一个位置，则该位置的左侧是左侧子树，右侧是右侧子树；

3. 遍历正确的子树，如果发现小于根的值二叉排序树中序遍历，则不符合二叉树搜索树的规则，则直接返回false；

4. 确定左右子树是否仍然是二叉搜索树（即，递归步骤1、2和3）.

代码如下:

    public static boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length < 1)
            return false;
        return judge(sequence, 0, sequence.length - 1);
    }
    private static boolean judge(int[] sequence, int left, int right) {
        // 只有一个节点，递归结束
        if(left >= right)
            return true;
        // 最右边的节点相当于根节点
        int t = sequence[right]; 
        // 用来记录序列中第一个比根节点大节点的下标
        int index = right;
        for (int i = left; i <= right - 1; i++) {
            // 找到根节点的右孩子
            if (sequence[i] > t) {
                index = i;
                i++;
                // 如果右子树中有比根节点还小的树的话，显然是不成立的。
                while (i <= right - 1) {
                    if(sequence[i] < t)
                        return false;
                    i++;
                }
            }
        }
        // 递归检查左右子树
        return judge(sequence, left, index - 1) && judge(sequence,index, right - 1);
    }

此分享来自公共微信的号码-强制农民使用的代码（di201805），作者: 英俊的地球

文本中详细说明了原始来源和转载的信息. 如果有任何侵权，请联系yunjia_community@tencent.com将其删除.

原始发表时间: 2019-03-28

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-167730-1.html