判断是不是二叉搜索树_

Java

想拿A高级磨洋工在写周报

分享下我的思路：

1、使用前序遍历，先判断当前节点的左右子节点，是否满足二叉搜索树；

2、使用递归函数，记录当前节点的父节点值，以及是否左节点；

3、如果是左节点，判断当前节点的右子节点值大于当前节点值且小于当前节点父节点值；

4、分别递归左子树和右子树。

public class Solution {
    
    public boolean isValidBST (TreeNode root) {
        return extracted(root, Integer.MAX_VALUE, false);
    }

    private boolean extracted(TreeNode root, int pre, boolean isLeft) {
        if (root == null) return true;
        if (root.left != null && root.left.val > root.val) {
            return false;
        }
        if (root.right!= null && (root.right.val < root.val || isLeft && root.right.val > pre)) {
            return false;
        }
        return extracted(root.left, root.val, true) && extracted(root.right, root.val, false);
    }
}

发表于 2025-12-18 15:43:06 回复(0)

Java

fixxx

java

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        return isValid(root.left,Integer.MIN_VALUE,root.val)&&isValid(root.right,root.val,Integer.MAX_VALUE);
    }

    public boolean isValid(TreeNode node , int minValue,  int maxValue){
        if(node==null) return true;
        if(node.val<minValue || node.val>maxValue) return false;
        boolean leftValid = isValid(node.left,minValue,node.val);
        boolean rightValid = leftValid&&isValid(node.right,node.val,maxValue);
        return leftValid&&rightValid;
    }

}

给递归加个最大值和最小值，感觉比较好理解，当左子树若不合法时，则右子树也没有必要再比较，有个剪枝的操作。

发表于 2025-09-21 16:26:43 回复(0)

Java

17c89

import java.util.*;

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

/**
 * NC184 判断是不是二叉搜索树
 * @author d3y1
 */
public class Solution {
    private boolean isBST = true;
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // return solution1(root);
        return solution2(root);
    }

    private TreeNode preNode;

    /**
     * 递归
     * @param root
     * @return
     */
    private boolean solution1(TreeNode root){
        inOrder(root);
        return isBST;
    }

    /**
     * 中序遍历
     * @param root
     */
    private void inOrder(TreeNode root){
        if(!isBST){
            return;
        }
        if(root == null){
            return;
        }

        inOrder(root.left);
        if(preNode == null){
            preNode = root;
        }else{
            if(preNode.val >= root.val){
                isBST = false;
                return;
            }else{
                preNode = root;
            }
        }
        inOrder(root.right);
    }

    ////////////////////////////////////////////////////////////////////////////////////////
    
    private Integer preVal = null;

    /**
     * 递归
     * @param root
     * @return
     */
    private boolean solution2(TreeNode root){
        inorder(root);
        return isBST;
    }

    /**
     * 中序遍历
     * @param root
     */
    private void inorder(TreeNode root){
        if(!isBST){
            return;
        }
        if(root == null){
            return;
        }

        inorder(root.left);
        if(preVal == null){
            preVal = root.val;
        }else{
            if(preVal >= root.val){
                isBST = false;
                return;
            }else{
                preVal = root.val;
            }
        }
        inorder(root.right);
    }
}

发表于 2025-01-14 12:41:55 回复(0)

Java

拿个offer就收手

思路一：判断中序序列是否递增

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) {
        if(root == null){
            return true;
        }
        List<Integer> list = new ArrayList<>();
        preOrder(list,root);
        for(int i=1;i<list.size();i++){
            if(list.get(i) < list.get(i-1)){
                return false;
            }
        }
        return true;
    }

    private void preOrder(List<Integer> list, TreeNode node) {
        if (node != null) {
            if (node.left != null) {
                preOrder(list, node.left);
            }
            list.add(node.val);
            if (node.right != null) {
                preOrder(list, node.right);
            }
        }
    }


}

思路2：递归判断每个节点是否符合二叉搜索树的性质

public class Solution {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        if (root == null) {
            return true;
        }
        preOrder(root);
        preOrder2(root);
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode p = stack.pop();
            // 判断该节点是否合法
            if(p.right != null){
                if(min.get(p.right) < p.val){
                    return false;
                }
                stack.push(p.right);
            }
            if(p.left != null){
                if(max.get(p.left) > p.val){
                    return false;
                }
                stack.push(p.left);
            }
        }
        return true;
    }

    HashMap<TreeNode, Integer> max = new HashMap<>();
    HashMap<TreeNode, Integer> min = new HashMap<>();

    private int preOrder( TreeNode node) {
        int val = node.val;
        if (node.left != null) {
            val = Math.max(preOrder(node.left), val);
        }
        if (node.right != null) {
            val = Math.max(preOrder(node.right), val);
        }
        max.put(node, val);
        return val;
    }

    // 返回node树中最大值
    private int preOrder2( TreeNode node) {
        int val = node.val;
        if (node.left != null) {
            val = Math.min(preOrder2(node.left), val);
        }
        if (node.right != null) {
            val = Math.min(preOrder2(node.right), val);
        }
        min.put(node, val);
        return val;
    }


}

发表于 2024-09-18 21:19:14 回复(0)

Java

୧⍢⃝୨

public class Solution {
    public boolean isValidBST (TreeNode root) {
        return isValid(root);
    }

    TreeNode pre;
    private boolean isValid(TreeNode root) {
        if (root == null) {
            return true;
        }

        boolean left = isValid(root.left);
        if (pre != null && pre.val > root.val) {
            return false;
        }
        pre = root;
        boolean right = isValid(root.right);
        return left && right;
    }
}

发表于 2024-09-08 18:45:43 回复(0)

Java

牛客348570162号

 // 使用中序遍历，就相当于一维数组，即前面一位小于当前位
    TreeNode pre = new TreeNode(Integer.MIN_VALUE);
    public boolean isValidBST (TreeNode root) {
        if(root == null) return true;
        if(!isValidBST(root.left)) return false;
        if(pre.val < root.val){
            pre = root;
        }else{
            return false;
        }
       if(!isValidBST(root.right)) return false;
       return true;
    }

发表于 2024-08-27 15:36:53 回复(0)

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 {
    // 封装要获得的信息
    public class Info {
        public int max;
        public int min;
        public boolean isBST;

        public Info() {
            this.max = Integer.MAX_VALUE;
            this.min = Integer.MIN_VALUE;
            this.isBST = true;
        }

        public Info(int max, int min, boolean isBST) {
            this.max = max;
            this.min = min;
            this.isBST = isBST;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here

        // 1.我要干什么：
        //        我要确定以root为根结点的子树是否是二叉搜索树

        // 2.我需要什么信息：
        //      获知【左子树】的【最大节点值】以及【是否二叉搜索树】
        //      获知【右子树】的【最小节点值】以及【是否二叉搜索树】
        //      综上所述，我需要左右子树的【最大和最小节点值】与【是否二叉搜索树】

        // 3.我如何利用两个子树的信息加工出来我的信息：
        //      若两棵子树均是二叉搜索树，且右 > root > 左，则true

        return process(root).isBST;
    }

    public Info process (TreeNode root) {
        // 递归出口
        if (root == null) {
            return new Info();
        }

        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        // 计算左右子树的真实最大值和最小值（如果为空，则置为root的值）
        int trueLeftMax = leftInfo.max != Integer.MAX_VALUE ? leftInfo.max : root.val;
        int trueLeftMin = leftInfo.min != Integer.MIN_VALUE ? leftInfo.min : root.val;
        int trueRightMax = rightInfo.max != Integer.MAX_VALUE ? rightInfo.max : root.val;
        int trueRightMin = rightInfo.min != Integer.MIN_VALUE ? rightInfo.min : root.val;
        // 计算本子树的最大值和最小值
        int myMax = Math.max(root.val, Math.max(trueLeftMax, trueRightMax));
        int myMin = Math.min(root.val, Math.min(trueLeftMin, trueRightMin));

        if (leftInfo.isBST == false || rightInfo.isBST == false) {
            // 两棵子树只要有一个不是二叉搜索树，直接false
            return new Info(myMax, myMin, false);
        }
        // 两棵子树都是二叉搜索树
        // 注意！这里的等号是为了让子节点为null时（即左右最大或最小结点的值与本结点值相同）通过判断
        if (trueLeftMax <= root.val && root.val <= trueRightMin) {
            // 且满足右min > root > 左max，则true
            return new Info(myMax, myMin, true);
        }
        return new Info(myMax, myMin, false);
    }
}

发表于 2024-08-01 00:22:45 回复(0)

Java

melo110

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) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //左右节点高度
        int lHeight = 1;
        int rHeight = 1;
        //如果右节点不为null,则队列下一个元素的左右子节点需高度减一
        int count = 0;
        boolean flag = true;
        while (!queue.isEmpty()) {
            TreeNode e = queue.poll();
            count++;
            if (e.left != null) {
                lHeight++;
                queue.add(e.left);
                flag = toBST(root, e.left, lHeight, 0, 0, 0);
                if (flag == false) {
                    return false;
                }
            }
            if (e.right != null) {
                rHeight++;
                queue.add(e.right);
                flag = toBST(root, e.right, rHeight, 0, 1, 1);
                if (flag == false) {
                    return false;
                }
                if (count % 2 == 0) {
                    lHeight--;
                    rHeight--;
                }
            }
        }
        return true;
    }

    //通过高度对比和子节点左右位置对比确定是否与平衡二叉树一致
    public boolean toBST(TreeNode root, TreeNode node, int height,
                                int currentHeight,
                                int position, int currentposition) {
        currentHeight++;
        if (currentHeight > height) {
            return false;
        }
        if (node.val == root.val) {
            //compare vertical height
            if (currentHeight != height) {
                return false;
            }
            //判断左右
            if (position == currentposition) {
                return true;
            }
        }
        if (node.val < root.val) {
            if (root.left == null) {
                return false;
            }
            return toBST(root.left, node, height, currentHeight, position, 0);
        }
        if (node.val > root.val) {
            if (root.right == null) {
                return false;
            }
            return toBST(root.right, node, height, currentHeight, position, 1);
        }
        return true;
    }


}

我的思路是根据从根节点遍历元素来构造二叉搜索树，根据节点高度和左右子节点位置是否一致来判断

1. 遍历元素且记录该元素高度和左右位置

2. 对比二叉平衡树看当前元素的高度和位置是否与二叉平衡树一致。不一致则返回false

发表于 2024-06-14 14:55:30 回复(0)

Java

22wli

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布尔型
     */
    List<Integer> res = new ArrayList<>();
    boolean flag = true;
    public boolean isValidBST (TreeNode root) {
        // write code here
        if ( root == null ) return true;
        midBST( root );

        return flag;
    }

    private void midBST(TreeNode root) {
        if (root.left != null) midBST( root.left );
        if ( res.size() > 0 && res.get(res.size() - 1) > root.val ) flag = false;
        res.add( root.val );
        if (root.right != null) midBST( root.right );
    }
}

直接检查中序遍历的结果是否有序

发表于 2024-04-25 21:37:06 回复(0)

Java

我也今晚打老虎

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        returnType res = judge(root);
        return res.isBST;
    }

    public returnType judge(TreeNode root) {
        // 递归：向左右子树索要信息：是否是BST；左子树最大值；右子树最小值
        returnType res = new returnType();
        if (root == null){
            res.isBST = true;
            return res;
        }
        returnType resLeft = judge(root.left);
        // 由于递归获取左树最大，右树最小，所以左右都要同时统计最大最小（左树也有右子树，右树也有左子树）：取信息并集
        res.max = Math.max(root.val, resLeft.max); // 左树最大最小值
        res.min = Math.min(root.val, resLeft.min);
        if(!resLeft.isBST || root.val < resLeft.max){ // 左树假或者根小于左，返回假
            return res; // returnType 默认 false
        }
        returnType resRight = judge(root.right);
        res.max = Math.max(root.val, resRight.max); // 右树最大最小值
        res.min = Math.min(root.val, resRight.min);
        if(!resRight.isBST || root.val > resRight.min){ // 右树假或者根大于右边，返回假
            return res; // returnType 默认 false
        }
        res.isBST = true;
        return res;
    }

    public class returnType {
        int max = Integer.MIN_VALUE; // 坑：最大要设为最小，最小要设为最大
        int min = Integer.MAX_VALUE;
        boolean isBST = false;
    }
}

编辑于 2024-04-11 18:06:03 回复(0)

Java

李克雷

public class Solution {

    private TreeNode pre = null;
    /**
     * 给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        if (null == root) {
            return false;
        }
        return inorder(root);
    }

    public boolean inorder(TreeNode curr) {
        if (null == curr) {
            return true;
        }
        boolean isLeftOK = inorder(curr.left);
        if (pre != null && pre.val >= curr.val) {
            return false;
        }
        pre = curr;
        boolean isRightOK = inorder(curr.right);
        return isLeftOK && isRightOK;
    }

}

发表于 2023-10-18 17:29:39 回复(0)

Java

牛客920655150号

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    boolean b = true;
    TreeNode t;
    public boolean isValidBST (TreeNode root) {
        // write code here
        //或者采用中序遍历搜索树一定有序来判断
        t = root;
        a(root);
        return b;
    }
    public void a(TreeNode root) {
        if (root == null||b==false)
            return;
        if (root.left != null) {
            if (root.left.val > root.val) {
                b = false;
                return;
            }
            if (t.val < root.val) {
                if (root.left.val < t.val) {
                    b = false;
                    return;
                }
            }
        }
        if (root.right != null) {
            if (root.right.val < root.val) {
                b = false;
                return;
            }
            if (t.val > root.val) {
                if (root.right.val > t.val) {
                    b = false;
                    return;
                }
            }
        }
        t = root;
        a(root.left);
        a(root.right);
    }
}

发表于 2023-10-12 15:00:43 回复(0)

Java

dqxfz

public class Solution {

Integer prev = null;

boolean result = true;

public boolean isValidBST (TreeNode root) {

// 二叉搜索树的中序遍历就是升序的，如果不满足当前节点大于前一个，那么就不是二叉搜索树

iterate(root);

return result;

}

private void iterate(TreeNode root) {

if (root == null) {

return;

}

if (result) {

iterate(root.left);

if (prev != null && root.val <= prev) {

result = false;

}

prev = root.val;

iterate(root.right);

}

发表于 2023-09-20 21:40:36 回复(0)

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布尔型

*/

TreeNode pre = null;

public boolean isValidBST (TreeNode root) {

// write code here

if(root==null)return true;

if(!isValidBST(root.left))return false;

if(pre!=null&&pre.val>root.val)return false;

pre=root;

if(!isValidBST(root.right))return false;

return true;

}

发表于 2023-07-29 21:07:35 回复(0)

Java

DDwu

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布尔型
     */
     int min =Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
        // write code here
        //return InOrder(root);
        return Dfs(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    public boolean Dfs (TreeNode root, int min, int max) {
        if (root == null) return true;
        if (root.val < min || root.val > max) return false;
        return Dfs(root.left, min, root.val) && Dfs(root.right, root.val, max);
    }
    public boolean InOrder (TreeNode root) {
        if (root == null) return true;
        if (!InOrder(root.left)) {
            return false;
        }
        if (root.val < min) {
            return false;
        } else {
            min=root.val;
        }
        if(!InOrder(root.right)) return false;
        return true;
    }

}

发表于 2023-07-27 13:00:49 回复(0)

Java

做则必成的勇气和信心

public boolean isValidBST (TreeNode root) {
        List<Integer> list=new ArrayList<>();
        build(root,list);
        for(int i=0;i<list.size()-1;i++){//list中的元素应该是递增的
            if(list.get(i)>=list.get(i+1)){
                return false;
            }
        }
        return true;
    }
    public void build(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        //中序遍历  左 头 右
        build(root.left,list);
        list.add(root.val);
        build(root.right,list);
    }

发表于 2023-07-12 14:58:02 回复(0)

Java

牛客667863907号

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here
        if (root == null) return true;
        int rootVal = root.val;
        boolean res = true;
        if (root.left != null) {
            if (rootVal < root.left.val) return false;
        }
        if (root.right != null) {
            if (rootVal > root.right.val) return false;
        }
        if (root.left != null) {
            res = getValidBST(root.left, rootVal, true);
        }
        if (!res) return res;
        if (root.right != null) {
            res = getValidBST(root.right, rootVal, false);
        }
        return res;
    }

    private boolean getValidBST(TreeNode root, int rootVal, boolean flag) {
        if (root == null) return true;
        int val = root.val;
        if (flag) {
            if(val > rootVal) return false;
            if (root.left != null) {
                if (val < root.left.val) return false;
            }
            if (root.right != null) {
                if (val > root.right.val ) return false;
            }
        } else {
            if(val < rootVal) return false;
            if (root.left != null) {
                if (val < root.left.val ) return false;
            }
            if (root.right != null) {
                if (val > root.right.val) return false;
            }
        }
        boolean res1 = getValidBST(root.left, rootVal, flag);
        boolean res2 = getValidBST(root.right, rootVal, flag);
        return res1 && res2;
    }
}

发表于 2023-03-22 23:39:18 回复(0)

判断是不是二叉搜索树

输入

输出

说明

输入

输出

说明

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题