Sword Finger Offer Java Edition面试问题33: 二叉搜索树的后遍历序列

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

public class Solution {
    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 mid = start;
        while (mid < end && sequence[mid] < sequence[end]) {
            mid++;
        }
        // 在二叉搜索树中右子树节点的值大于根节点的值
        for (int i = mid + 1; i < end; i++) {
            if (sequence[i] < sequence[end]) {
                return false;
            }
        }
        // 判断左子树和右子树是不是二叉搜索树
        return verify(sequence, start, mid - 1) && verify(sequence, mid, end - 1);
    }
}

Sword Finger Offer Java Edition目录

Sword Finger Offer Java Edition主题

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