首页 > 试题广场 >

判断是不是二叉搜索树

[编程题]判断是不是二叉搜索树
  • 热度指数：111651 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。

二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。

例：
图1

图2

数据范围：节点数量满足 ，节点上的值满足
示例1

输入

{1,2,3}

输出

false

说明

如题面图1
示例2

输入

{2,1,3}

输出

true

说明

如题面图2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Javascript
canoelu头像 canoelu 
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */

function isValidBST(root) {
    // 1. 初始化变量
    // 栈数组
    const stack = [];
    // 游标 current
    let current = root;
    // 记录前一个节点
    let pre = null;
    while (stack.length > 0 || current !== null) {
        // 1. 中序遍历的套路 不断遍历 把游标的节点加入栈
        if (current) {
            stack.push(current);
            // 2. 不断遍历左子树 节点 加入栈
            current = current.left;
        } else {
            // 3. 如果碰到了叶子节点 就取出栈的元素 判断值是否小于上一个节点的值
            current = stack.pop();
            // 4. 如果小于 证明不是二叉搜索树 因为二叉搜索树 左 - 中 - 右 应该是递增的顺序
            if (pre !== null && current.val < pre.val) {
                return false;
            }
            // 5. 修改上一个节点的值 为当前的节点
            pre = current;
            // 6. 中序遍历 修改游标
            current = current.right;
        }
    }
    return true
}
module.exports = {
    isValidBST: isValidBST,
};

编辑于 2024-03-14 16:30:03 回复(0)
Javascript
wuster6016头像 wuster6016
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */
//二叉收索树的中序遍历是递增的
function inorder(root, arr = []) {
  if (root) {
    inorder(root.left, arr);
    arr.push(root.val);
    inorder(root.right, arr);
  }
  return arr;
}

// function judge(root, flag = "", val = 0) {
//   if (root == null || (root.left == null && root.right == null)) return true; //根为null或左右子树都为null
//   if (root) {
//     //不满足二叉收索树
//     if (root.val <= root.left.val || root.val >= root.right.val) return false;
//     //满足二叉收索树
//     else if (root.val > root.left.val && root.val < root.right.val) {
//       if (flag == "left" && root.right.val > val) return false;
//       if (flag == "right" && root.left.val < val) return false;
//       //判断左右子树是否是二叉收索树
//       return (
//         judge(root.left, "left", root.val) &&
//         judge(root.right, "right", root.val)
//       );
//     }
//   }
// }

function isValidBST(root) {
  if (root == null || (root.left == null && root.right == null)) return true;
  let inarr = inorder(root);
  let temp = [...inarr];
  temp.sort((a, b) => a - b);
  for (let i = 0; i < inarr.length; i++) {
    if (temp[i] != inarr[i]) return false;
  }
  return true;
}
module.exports = {
  isValidBST: isValidBST,
};

发表于 2022-09-29 21:26:01 回复(1)
Javascript
Xinleidebaby头像 Xinleidebaby 
function isValidBST( root ) {
    // write code here
    //中序遍历
    let a=[]
    function mid(root){
        if(!root) return 
        mid(root.left)
        a.push(root.val)
        mid(root.right)
    }
    //写完了别忘记调用呀
    mid(root)
    for(let i=0;i<=a.length-2;i++){
        if(a[i]>a[i+1])
            return false
    }
    return true
}

发表于 2022-08-02 11:49:19 回复(0)
Javascript
Five鱼头像 Five鱼
// js迭代
let min = Math.pow(-2,31);
function isValidBST( root ) {
    // write code here
//     迭代
    let prev = min;
    let cur ;
    let stack = [];
    let p = root;
    while(p||stack.length){
        while(p){
            stack.push(p);
            p = p.left;
        }
        let node = stack.pop();
        if(node.val <prev){
            return false;
        }else{
            prev = node.val;
        }
        p = node.right;
    }
    return true;
}
module.exports = {
    isValidBST : isValidBST
};
发表于 2022-06-27 15:54:30 回复(0)
Javascript
萌萌94头像 萌萌94
function isValidBST( root ) {
    // write code here
    let pre = null, cur, error = false;
    const midorder = (root) => {
        if (!root) return;
        if (error) return;
        
        midorder(root.left);
        // check
        cur = root.val;
        if (pre !== null && pre >= cur) {
            error = true;
        }
        pre = cur;
        
        midorder(root.right);
    }
    
    midorder(root);
    return !error;
}
发表于 2022-05-22 09:49:59 回复(0)
Javascript
找工作中ings头像 找工作中ings
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */  
// 递归的方法    思想：左右子树都是二叉搜索树，进行分别判断 
// 首先是根节点没有范围限制，在（-Infinity,Infinity）
function isValidBST( root ) {
    // write code here
    return helper(root,-Infinity,Infinity)
    
}
const helper = ((root,lower,upper)=>{
    if(root === null) return true
    if(root.val <= lower || root.val >= upper) return false
    return helper(root.left,lower,root.val)&&helper(root.right,root.val,upper)
    
})
module.exports = {
    isValidBST : isValidBST
};
发表于 2022-03-15 18:00:21 回复(0)
提交观点

问题信息

树
难度：
7条回答 5437浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断是不是二叉搜索树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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