请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

关于二叉搜索树的问题

您好,老师。根据您的思路,解决的函数可以解决大部分场景。但是有一个场景,无法解决。请老师帮忙看一下。
以下是leetcode的题。当输入值为 [10,5,15,null,null,6,20] 时,解题错误。
主要的问题在于节点6,6小于父节点15,且在父节点的左边,但是6小于根节点10,且在根节点的右边。
var isValidBST = function(root) {
    if (!root) {
        return true
    }
    return judge(root)
};

function judge(node) {
    if (!node.left && !node.right) {
        return true
    }
    if (node.left && node.left.val>=node.val) {
        return false
    }
    if (node.right && node.right.val<=node.val) {
        return false
    }
    return judge(node.left) && judge(node.right)
}

图片描述

正在回答 回答被采纳积分+3

1回答

快乐动起来呀 2020-02-21 22:13:20

你把null改成0试试呢?

0 回复 有任何疑惑可以回复我~
  • 提问者 meimei1314 #1
    老师,关于这个问题,如果换成是0,会在根节点的左子树5的判断过程中判断为false,不会再执行根节点的右子树15的判断。
    这个问题的核心就在于,在判断右子树的过程出了纰漏。
    根节点的右子树15确实大于根节点10,满足二叉树条件。
    
    根节点右子树15的左子树6确实小于根节点右子树15,满足条件。但是它却小于根节点10,不满足二叉树条件。
    
    本次判断题中,我们只判断了一个节点和它的两个子节点是否满足二叉树的条件,没有判断它的两个子节点和节点的父节点是否满足二叉树的条件。
    
    请问,遇到这样的题目,我应该如何做呢?
    回复 有任何疑惑可以回复我~ 2020-02-23 13:32:41
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信