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

知识点

树，二叉搜索树

解题思路

根据二叉搜索树的性质，左节点值要小于根节点，右节点值要大于根节点。

我们举个例子比如这颗树，根节点为6，

它有左子树，左子树要求是要小于6，4满足要求。再看节点4有左右子树，左子树为3满足小于4的要求，右子树5，这时右子树需要满足的要求就是需要大于4，并且小于6。右子树要求既要大于父节点，又要小于父节点小于的树。

因此每一个节点都需要满足的条件是一个范围，左子树要小于父节点，并且要大于父节点大于的值。

右子树要大于父节点，并且要小于父节点小于的值。

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布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here
        return check(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
    }

    public boolean check(TreeNode root, int leftNum, int rightNum){
        if(root.val < leftNum || root.val > rightNum) return false;
        boolean ans = true;
        if(root.left != null){
            ans = ans && check(root.left,leftNum,root.val);
        }
        if(root.right != null){
            ans = ans && check(root.right,root.val,rightNum);
        }
        return ans;
    }
}