美文网首页
验证二叉搜索树

验证二叉搜索树

作者: 小白学编程 | 来源:发表于2018-09-02 14:57 被阅读0次

    给定一个二叉树,判断其是否是一个有效的二叉搜索树。

    假设一个二叉搜索树具有如下特征:

    节点的左子树只包含小于当前节点的数。
    节点的右子树只包含大于当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。

    image.png
    class Solution {
        public boolean isValidBST(TreeNode root) {
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }
        
        public boolean isValidBST(TreeNode root,long min,long max){
            if(root==null){
                return true;
            }
            if(root.val<=min||root.val>=max){
                return false;
            }
            return isValidBST(root.left,min,root.val)&&isValidBST(root.right,root.val,max);
        }
        
    }
    

    思路

    只要判断该二叉树,二叉搜索树的中序遍历顺序是升序的

    class Solution {
        public boolean isValidBST(TreeNode root) {
            List<Integer> list = new ArrayList<Integer>();
            inOrder(root, list);
            System.out.print(list);
            for (int i = 1; i < list.size() ; ++i) {
                if (list.get(i-1) >= list.get(i )) return false;
            }
            return true;
            
        }
        public void inOrder(TreeNode node, List<Integer> list) {
            if (node == null) return;
            inOrder(node.left, list);
            list.add(node.val);
            inOrder(node.right, list);
        }
        
    }
    
    

    相关文章

      网友评论

          本文标题:验证二叉搜索树

          本文链接:https://www.haomeiwen.com/subject/pxjmwftx.html