关于java:LeetCode098验证二叉搜索树

39次阅读

共计 1249 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：给定一个二叉树，判断其是否是一个无效的二叉搜寻树。

假如一个二叉搜寻树具备如下特色：

节点的左子树只蕴含小于以后节点的数。

节点的右子树只蕴含大于以后节点的数。

所有左子树和右子树本身必须也是二叉搜寻树。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：递归法

依据二叉搜寻树的性质，以后节点左子树的上边界（不蕴含）和右子树的下边界（不蕴含）是以后节点的值，所以能够用递归的办法来解决，递归过程如下：

根节点没有父结点，所以第一次调用递归办法高低边界应用最大最小值；

如果以后节点为 null，阐明是叶子节点，间接返回 true；

如果以后节点的值不在高低边界范畴内，返回 false；

递归判断以后节点的左右节点是否在相应的上线边界范畴内。

import com.kaesar.leetcode.TreeNode;

public class LeetCode_098 {
    /**
     * 递归法
     *
     * @param root
     * @return
     */
    public static boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    /**
     * 递归办法
     *
     * @param node 以后节点
     * @param low  以后节点的下边界（不蕴含）* @param high 以后节点的上边界（不蕴含）* @return
     */
    private static boolean isValidBST(TreeNode node, long low, long high) {
        // 如果 node 为 null，阐明是叶子节点，间接返回 true
        if (node == null) {return true;}
        // 如果以后节点的值不在高低边界范畴内，返回 false
        if (node.val <= low || node.val >= high) {return false;}

        // 递归判断以后节点的左右节点是否在相应的上线边界范畴内
        return isValidBST(node.left, low, node.val) && isValidBST(node.right, node.val, high);
    }

    public static void main(String[] args) {TreeNode root = new TreeNode(5);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(6);

        System.out.println(isValidBST(root));
    }
}