【算法】判断是否为二叉搜索树

二叉搜索树(也叫二叉排序树、二叉查找树,Binary Search Tree),或是空树,或是满足以下性质的二叉树:

  • 若左子树不空,则左子树所有节点的值均小于其根节点值
  • 其右子树不空,则右子树所有节点的值均大于其根节点值
  • 左右子树也分别是一颗二叉搜索树

由二叉搜索树性质,当对其进行中序遍历时,结果是递增序列。所有可以通过中序遍历的思想判断是否为一颗二叉搜索树。

public class IsBST {

    //静态全局变量,保存中序遍历中上一个节点的值
    public static int preValue = Integer.MIN_VALUE;
    //递归中序遍历判断是否是二叉搜索树
    public static boolean isBST(Node<Integer> head) {
        if (head == null) {
            return true;
        }
        boolean isLeftBst = isBST(head.left);
        if (!isLeftBst) {
            return false;
        }
        if (head.value <= preValue) {
            return false;
        } else {
            preValue = head.value;
        }
        return isBST(head.right);
    }

    //非递归中序遍历判断是否为二叉搜索树
    public static boolean isBST2(Node<Integer> head) {
        if (head != null) {
            int preValue = Integer.MIN_VALUE;
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    //若当前值比上一个值大则不是二叉搜索树
                    if (head.value <= preValue) {
                        return false;
                    } else {
                        preValue = head.value;
                    }

                    head = head.right;
                }
            }
        }
        return true;
    }

    //方法三 树型DP(树型动态规划)
    public static boolean isBST3(Node<Integer> head) {
        return process(head).isBST;
    }
    public static class ReturnData {
        public boolean isBST;
        public int min;
        public int max;

        public ReturnData(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }
    public static ReturnData process(Node<Integer> x) {
        if (x == null) {
            return null;
        }
        ReturnData leftData = process(x.left);
        ReturnData rightData = process(x.right);

        int min = x.value;
        int max = x.value;
        if (leftData != null) {
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }
        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }

        boolean isBST = true;
        if (leftData != null && (!leftData.isBST || leftData.max >= x.value)) {
            isBST = false;
        }
        if (rightData != null && (!rightData.isBST || rightData.min <= x.value)) {
            isBST = false;
        }
        return new ReturnData(isBST, min, max);
    }
}
上一篇:Leetcode70场双周赛-第二题2145.统计隐藏数组数目


下一篇:【数组】4:盛最多水的容器