Java题解 | #牛群中的编号是否有效#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */

    // write code here
    /**
    * 判断给定的二叉树是否为二叉搜索树（BST）
    * @param root 二叉树的根节点
    * @return 若是二叉搜索树则返回true，否则返回false
    */
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    /**
     * 辅助方法，判断以当前节点为根的子树是否为二叉搜索树
     * @param node 当前节点
     * @param minVal 当前节点值的下界
     * @param maxVal 当前节点值的上界
     * @return 若以当前节点为根的子树是二叉搜索树则返回true，否则返回false
     */
    private boolean isValidBST(TreeNode node, long minVal, long maxVal) {
        // 若当前节点为空，表示该子树有效，返回true
        if (node == null) {
            return true;
        }

        // 若当前节点的值超出上下界范围，不满足二叉搜索树定义，返回false
        if (node.val <= minVal || node.val >= maxVal) {
            return false;
        }

        // 递归判断左右子树是否为二叉搜索树，并更新上下界范围
        return isValidBST(node.left, minVal, node.val) &&
               isValidBST(node.right, node.val, maxVal);
    }
}

这道题考察的是 二叉搜索树 的判断。BST是一种特殊的二叉树，其中任意节点的左子树中的值小于该节点的值，右子树中的值大于该节点的值。

该代码通过递归的方式来判断给定的二叉树是否为BST。具体解释如下：

• isValidBST(TreeNode root)方法是对外的接口，用于判断给定的二叉树root是否为BST。它调用了辅助方法isValidBST(TreeNode node, long minVal, long maxVal)来进行判断。
• isValidBST(TreeNode node, long minVal, long maxVal)方法用于判断以当前节点node为根的子树是否为BST。minVal和maxVal分别表示当前节点值的下界和上界，用于限制当前节点的值范围。
• 首先，如果当前节点为null，说明该子树有效，返回true。
• 然后，判断当前节点的值是否超出了指定的范围，如果超出了范围，则不满足BST定义，返回false。
• 最后，递归地判断当前节点的左子树和右子树是否为BST，通过更新minVal和maxVal的值，将约束范围传递给下一层递归。如果左右子树都是BST且满足当前节点的值约束，则返回true，否则返回false。

代码中使用了long类型的minVal和maxVal，是为了处理特殊情况，即节点值等于Long.MIN_VALUE或Long.MAX_VALUE的情况。

这种递归的解法时间复杂度为O(n)，其中n为二叉树的节点个数。通过递归遍历二叉树的每个节点，并进行值的比较，判断是否满足BST的定义。