关于二叉搜索树的问题

来源：11-4 验证二叉搜索树-代码实操

meimei1314

2020-02-21

您好，老师。根据您的思路，解决的函数可以解决大部分场景。但是有一个场景，无法解决。请老师帮忙看一下。
以下是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)
}

图片描述

写回答

1回答

快乐动起来呀

2020-02-21

你把null改成0试试呢？

meimei1314

老师，关于这个问题，如果换成是0，会在根节点的左子树5的判断过程中判断为false，不会再执行根节点的右子树15的判断。这个问题的核心就在于，在判断右子树的过程出了纰漏。根节点的右子树15确实大于根节点10，满足二叉树条件。根节点右子树15的左子树6确实小于根节点右子树15，满足条件。但是它却小于根节点10，不满足二叉树条件。本次判断题中，我们只判断了一个节点和它的两个子节点是否满足二叉树的条件，没有判断它的两个子节点和节点的父节点是否满足二叉树的条件。请问，遇到这样的题目，我应该如何做呢？

2020-02-23

共1条回复

JavaScript版数据结构与算法

填补前端同学的算法短板，掌握面试中最常见的算法与数据结构

2467 学习 · 395 问题

查看课程

相似问题

既然构建二叉树的时候都是先放左节点为什么还会出现 !left&&right 的情况

回答 3

二叉树的构建关联关系问题

回答 1

老师，我觉得这个代码逻辑有问题，如果左子树的右子树的值大于父节点的值呢？按你这个逻辑是不是就不通了

回答 4

关于二叉树的关联关系

回答 1

老师，你验证的代码逻辑应该是有问题的

回答 1

打开慕课网App查看更多内容