题目

实现一个函数,检查一棵二叉树是否为二叉搜索树。

代码

中序遍历

    TreeNode pre = null;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (pre != null && root.val <= pre.val) return false;
        pre = root;
        if (!isValidBST(root.right)) return false;
        return true;
    }

根据二叉搜索树特点判断

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }
        return min < node.val && node.val < max && isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }