首页 > 试题广场 >

判断二叉搜索树

[编程题]判断二叉搜索树
  • 热度指数：18814 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
判断给出的二叉树是否是一个二叉搜索树（BST）
二叉搜索树的定义如下
  • 一个节点的左子树上节点的值都小于自身的节点值
  • 一个节点的右子树上节点的值都大于自身的节点值
  • 所有节点的左右子树都必须是二叉搜索树
如果你不清楚“{1,#,2,3}"的含义的话，请继续阅读
我们用如下方法将二叉树序列化：
二叉树的序列化遵循层序遍历的原则，”#“代表该位置是一条路径的终结，下面不再存在结点。
例如： 
    1
   / \
  2   3
     /
    4
     \
      5
上述的二叉树序列化的结果是："{1,2,3,#,#,4,#,#,5}".
示例1

输入

{1,1}

输出

false
示例2

输入

{0,#,1}

输出

true

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
tuweilong头像 tuweilong 
/*
中序遍历。序列递增则为BST。
注意:遇到相同元素时，需要放在左子树上。
*/
import java.util.*;
public class Solution {
    private ArrayList<Integer> list = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        leftRootRight(root);
        int len = list.size();
        for (int i = 1; i < len; i++) {
            if (list.get(i) <= list.get(i - 1))
                return false;
        }
        return true;
    }
    
    public void leftRootRight(TreeNode root) {
        if (root == null) return;
        leftRootRight(root.left);
        list.add(root.val);
        leftRootRight(root.right);
    }
}

发表于 2019-06-20 14:50:58 回复(0)
更多回答
てんდちん头像 てんდちん 
综合大家思路:总结三种方法
// method 1 : timeComplex（n^2） spaceComplexit（n）
    public boolean isValidBST1(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSubTreeLess(root.left, root.val) && isSubTreeGreater(root.right, root.val) && isValidBST1(root.left)
                && isValidBST1(root.right);
    }

    private boolean isSubTreeLess(TreeNode p, int val) {
        if (p == null) {
            return true;
        }
        return p.val < val && isSubTreeLess(p.left, val) && isSubTreeLess(p.right, val);
    }

    private boolean isSubTreeGreater(TreeNode p, int val) {
        if (p == null) {
            return true;
        }
        return p.val > val && isSubTreeGreater(p.left, val) && isSubTreeGreater(p.right, val);
    }

    // method 2 : runtime O(n) spaceComplexity (n)
    public boolean isValidBST2(TreeNode root) {

        return valid(root, null, null);
    }

    private boolean valid(TreeNode root, Integer low, Integer high) {
        if (root == null) {
            return true;
        }

        return (low == null || root.val > low) && (high == null || root.val < high) && valid(root.left, low, root.val)
                && valid(root.right, root.val, high);
    }

    // method 3 : method 2 : runtime O(n) spaceComplexity (n) in-order traversal
    private TreeNode prev;
    public boolean isValidBST3(TreeNode root) {
        prev = null;
        return isMonotonicIncreasing(root);
    }

    private boolean isMonotonicIncreasing(TreeNode p) {
        if (p == null) {
            return true;
        }
        if (isMonotonicIncreasing(p.left)) {
            if (prev != null && p.val <= prev.val) {
                return false;
            }
            prev = p;
            return isMonotonicIncreasing(p.right);
        }
        
        return false;
    }

发表于 2018-04-28 09:49:58 回复(0)
JacobGo！头像 JacobGo！ 
/*
	 * 方法一：利用二叉树的中序遍历
	 */
	public boolean isValidBST(TreeNode root) {
		if (root == null)
			return true;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		TreeNode pre = null;
		while (!stack.isEmpty() || cur != null) {
			if (cur == null) {
				cur = stack.pop();
				if (pre != null && pre.val >= cur.val)
					return false;
				pre = cur;
				cur = cur.right;
			} else {

				stack.push(cur);
				cur = cur.left;
			}
		}
		return true;
	}

发表于 2017-08-05 10:17:19 回复(1)
Java
丫丁头像 丫丁 
//方法1：每个结点都对应一个上限，一个下限。
public boolean isValidBST(TreeNode root) {
    return isValidRoot(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
public boolean isValidRoot(TreeNode root,int lower,int upper){
    if(root==null) return true;
    if(root.val<=lower || root.val>=upper) return false;
    return isValidRoot(root.left,lower,root.val)
            && isValidRoot(root.right,root.val,upper);
}
//方法2：中序遍历，记录前一个结点，与当前结点的值比较。
public class Solution {
    TreeNode pre;
    boolean isValidBST=true;
    public boolean isValidBST(TreeNode root) {
        inTraversal(root);
        return isValidBST;
    }
    public void inTraversal (TreeNode root){
        if(root==null) return ;
        inTraversal(root.left);
        if(pre!=null&&pre.val>=root.val) isValidBST=false;
        pre=root;
        inTraversal(root.right);
    }
}

编辑于 2017-05-03 14:52:45 回复(3)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        return solve(root,INT_MIN,INT_MAX);
    }
    bool solve(TreeNode *root,int l,int h) 
    {
    	if(root == NULL)
    		return true;
    	if(root->val <= l || root->val >= h)
    		return false;
    	return (solve(root->left,l,root->val) && solve(root->right,root->val,h));
	}
};

发表于 2017-08-31 02:48:29 回复(0)
闻思头像 闻思 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool helper(TreeNode * root, int lower, int upper) {
        if(!root) {
            return true;
        }
        if(root->val <= lower || root->val >= upper)	return false;
        return (helper(root->left, lower, root->val) && helper(root->right, root->val, upper));
    }
    
    bool isValidBST(TreeNode *root) {
        return helper(root, INT_MIN, INT_MAX);
    }
};

发表于 2016-10-01 19:38:18 回复(0)
coollyn头像 coollyn 
class Solution 
{
public:
    bool isValidBST(TreeNode *root) 
    {
        if(!root)
            return true;
        
        if(!isValidBST(root->left))
            return false;
        
        if(pre>=root->val)
            return false;
        pre=root->val;
        
        if(!isValidBST(root->right))
            return false;
        
        return true;
    }
private:
    int pre=INT_MIN;
};

发表于 2017-10-08 22:35:07 回复(0)
Java
詆調壹點头像 詆調壹點 
import java.util.*;
public class Solution {
    public boolean isValidBST(TreeNode root) {
		List<TreeNode> list = new ArrayList<>();
		inorder(root, list);
		for (int i = 1; i < list.size(); i ++) {
			if(list.get(i).val <= list.get(i - 1).val) return false;
		}
		return true;
	}
	public static void inorder(TreeNode root, List<TreeNode> list) {
		if(root != null) {
			inorder(root.left, list);
			list.add(root);
			inorder(root.right, list);
		}
	}
}

发表于 2017-04-15 15:24:33 回复(1)
六丶六头像 六丶六 
public class Solution {
    private TreeNode lastNode = null;
    private boolean isBST = true;
    public boolean isValidBST (TreeNode root) {
        if(root == null) return isBST;
        InOrder(root);
        return isBST;
    }
     public void InOrder(TreeNode root)
    {
        if(root == null) return;
        InOrder(root.left);
        if(lastNode != null)
        {
            if(lastNode.val >= root.val)
            {
                isBST = false;
            }
        }
        lastNode = root;
        InOrder(root.right);
    }
}

发表于 2020-09-13 22:19:53 回复(0)
Dancer_Wu头像 Dancer_Wu
中序遍历，中序二叉线索树的思路。记录前驱节点 
class Solution {
public:
    bool isMinOrder(TreeNode *root,TreeNode *&pre)
{
	if (!root) return true;
	if (!isMinOrder(root->left,pre)) return false ;
	if (pre&&pre->val >= root->val) return false;
	pre = root;
	return isMinOrder(root->right, pre);
}
    bool isValidBST(TreeNode *root) {
        TreeNode *pre = NULL;
	return isMinOrder(root, pre);
    }
};


发表于 2020-04-17 20:46:18 回复(0)
ExtraLocker头像 ExtraLocker 
class Solution {
public:
    // 中序遍历，两两比较
    TreeNode *prev = nullptr;
    bool isValidBST(TreeNode *root) {
        if (root == nullptr) return true;
        bool res = true;
        res &= isValidBST(root->left);
        if (prev != nullptr) res = res && prev -> val < root-> val;
        prev = root;
        res &= isValidBST(root->right);
        return res;
    }
};

发表于 2020-03-31 21:10:13 回复(0)
我寻思这打野走位就尼玛离谱儿头像 我寻思这打野走位就尼玛离谱儿 
public class Solution {
    TreeNode pre=new TreeNode(Integer.MIN_VALUE);
    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }
    boolean inorder(TreeNode root)
    {
        if(root==null)
            return true;
        boolean a=inorder(root.left);
        if(pre.val>=root.val)
            return false;
        pre=root;
        boolean b=inorder(root.right);
        return a&&b;
    }
}

发表于 2019-12-28 23:56:45 回复(0)
C/C++
J.Fan头像 J.Fan 
//比较Low的思路，把中序遍历序列保存下来判断是不是升序
class Solution {
public:
    vector<int> v;
    void midTrav(TreeNode *root)
    {
        if(root==NULL)
            return;
        midTrav(root->left);
        v.push_back(root->val);
        midTrav(root->right);
    }
    bool isValidBST(TreeNode *root) {
        if(root==NULL)
            return true;
        midTrav(root);
        int len = v.size();
        for(int i=0;i<len-1;i++)
        {
            if(v[i]>=v[i+1])
                return false;
        }
        return true;
    }
};

发表于 2018-10-08 17:39:18 回复(0)
HW柯可头像 HW柯可 
//中序遍历非递归算法，设置一个前指针pre，记录当前节点的前一节点的值，并与当前节点的值进行比较
import java.util.*;
public class Solution {
    public boolean isValidBST(TreeNode root) {
         if(root==null)
             return true;
         Stack<TreeNode> stack=new Stack<>();
         TreeNode pre=null;
         TreeNode node=root;
         while(node!=null||!stack.isEmpty()){
             if(node!=null){
                 stack.push(node);
                 node=node.left;
             }
             else{
                 node=stack.pop();
                 if(pre!=null&&pre.val>=node.val){
                     return false;
                 }
                 pre=node;
                 node=node.right;
             }
         }
        return true;
    }
}
    //中序遍历的递归算法(运行超时，无法通过，忘大佬门解答是不是哪里出错了)
 /* import java.util.*;
public class Solution {
    public boolean isValidBST(TreeNode root) {
         if(root==null)
             return true;
         List<TreeNode> list=inorder(root);
         for(int i=0;i<list.size()-1;i++){
             if(list.get(i).val>=list.get(i+1).val){
                 return false;
             }
             else{
                 return false;
             }
         }
        return true;
    }
    public List<TreeNode> inorder(TreeNode root){
        if(root==null)
            return new ArrayList<TreeNode>();
        List<TreeNode> list=new ArrayList<>();
        list.addAll(inorder(root.left));
        list.add(root);
        list.addAll(inorder(root.left));
        return list;
    }
}*/
-----------更正，借鉴了上面大佬的递归写法,通过了---------------
//中序遍历的递归算法
import java.util.*;
public class Solution {
    public boolean isValidBST(TreeNode root) {
         if(root==null)
             return true;
         List<TreeNode> list=new ArrayList<>();
         inorder(root,list);
         for(int i=0;i<list.size()-1;i++){
             if(list.get(i).val>=list.get(i+1).val){
                 return false;
             }
         }
        return true;
    }
    public static void inorder(TreeNode root,List<TreeNode> list){
        if(root!=null){
            inorder(root.left,list);
            list.add(root);
            inorder(root.right,list);
        }
    }
}

编辑于 2018-09-24 12:10:31 回复(0)
Java
华科平凡头像 华科平凡

java代码

一开始遍历到一个数组中，然后判断这个数组是否等于它的排序数组，但发现题目中要求二叉树必须是严格递增的，也就是说[1, 1]不是一棵bst。所以只能一个一个的元素遍历判断了：

public class Solution {
    private ArrayList<Integer> vals = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {
        midTraversal(root);
//        ArrayList<Integer> clone = Collections.sort((ArrayList<Integer>) vals.clone();
        for(int i = 0; i < vals.size() - 1; i++){
            if(vals.get(i) >= vals.get(i + 1))
                return false;
        }
        return true;
    }

    private void midTraversal(TreeNode root) {
        if (root == null)
            return;
        midTraversal(root.left);
        vals.add(root.val);
        midTraversal(root.right);
    }
}
发表于 2018-07-18 13:36:26 回复(0)
牛客3694799号头像 牛客3694799号 
//不断更新当前结点的大小域。很好理解的递归方法
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        return isValidBST(root, NULL, NULL);
    }

    bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max){
        if(!root)
            return true;
        if(min && root->val <= min->val)
            return false;
        if(max && root->val >= max->val)
            return false;
        return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
    }
};
发表于 2018-02-12 21:43:39 回复(0)
C/C++
黄汉韬头像 黄汉韬 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/*
思路：
使用中序遍历
*/
class Solution {
public:
    TreeNode *pre;
    bool isValidBST(TreeNode* root) {
        int res = 1;
        pre = NULL; // 中序遍历序列当前节点的前一个节点

        inorder(root, res);
        if (1 == res) {
            return true;
        }
        else {
            return false;
        }
    }

    void inorder(TreeNode *root, int &res) {
        if (!root) return ;
        inorder(root->left, res);
        if (NULL == pre) {
            pre = root;
        } else {
            if (root->val <= pre->val) {
                res = 0;
                return ;
            }
            pre = root;
        }
        inorder(root->right, res);
    }
};
发表于 2017-11-23 16:26:56 回复(0)
sky_头像 sky_ 
class Solution {
public:
    bool isValidBST(TreeNode *root) {
         return  dfs(root,-2e9,2e9);
    }
    bool dfs(TreeNode *root,int l,int r){
         if(!root) return true;
         if(root->val<=l||root->val>=r) return false;
         return dfs(root->left,l,root->val)&&dfs(root->right,root->val,r);
    }
};

发表于 2017-08-21 10:19:11 回复(1)
LinuX18头像 LinuX18 
 bool isValidBST(TreeNode *root) 
    {
        return inorderTravel(root);
    }
    bool inorderTravel(TreeNode *root)
    {
        if(root==nullptr)
            return true;
         stack<TreeNode *> st;
         TreeNode *cur = root,*pre = nullptr;
        while(st.size() || cur)
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            if(pre && pre->val >= cur->val)
                return false;
            st.pop();
            pre = cur;
            cur = cur->right;
        }
        return true;
    }

发表于 2017-07-09 15:14:28 回复(0)
Java
ephonzhang头像 ephonzhang 
public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        boolean judge = true;
        TreeNode leftMaxNode;
        TreeNode rightMinNode;
        if (root.left != null) {
            leftMaxNode = root.left;
            while (leftMaxNode.right != null) {
                leftMaxNode = leftMaxNode.right;
            }
            judge = judge && (leftMaxNode.val < root.val);
        }
        if (root.right != null) {
            rightMinNode = root.right;
            while (rightMinNode.left != null) {
                rightMinNode = rightMinNode.left;
            }
            judge = judge && (rightMinNode.val > root.val);
        }

        return judge && isValidBST(root.left) && isValidBST(root.right);

    }
}
编辑于 2017-04-27 22:33:03 回复(0)
提交观点

问题信息

树
难度：
95条回答 17388浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号