检查二进制搜索树是否为有效的javascript
检查二进制搜索树是否为有效的javascript
提问于 2015-12-02 22:13:05
我在网上遇到了这个问题，我找到了以下函数来检查BST是否有效。然而，我不能完全理解的是，max/min是如何从null变为您可以比较的值的。所以在下面的函数中：
//Give the recursive function starting values:
function checkBST(node) {
// console.log(node.right);
return isValidBST(node, null, null);
}
function isValidBST(node, min, max) {
console.log(min, max);
if (node === null) {
return true;
}
if ((max !== null && node.val > max) || (min !== null && node.val < min)) {
return false;
}
if (!isValidBST(node.left, min, node.val) || !isValidBST(node.right, node.val, max)) {
return false;
}
return true;
}
var bst = new BinarySearchTree(8);
bst.insert(3);
bst.insert(1);
bst.insert(6);
bst.insert(10);
bst.insert(4);当你从左边的最低深度返回时，它会将最低深度处的值与其正上方的深度进行比较(即当输出为1 3时)。不知何故，min从null变成了1，我看不出是怎么回事，我在想，你需要一些基本情况才能让最小值从null变成其他值……当我在每次运行时console.log最小/最大值时，我在控制台中得到了这个。
null null
null 8
null 3
null 1
1 3
3 8
3 6
3 4
4 6
6 8
8 null
8 10
10 null回答 4
Stack Overflow用户
回答已采纳
发布于 2015-12-04 00:32:29
变量min将变为非null，因为您显式地调用
isValidBST(node.right, node.val, max)
其中，您将node.val作为参数min进行传递。一定是在你进行这个调用的时候，node.val不是空的；
Stack Overflow用户
发布于 2018-10-08 01:52:21
给定一个节点，验证二进制搜索树，确保每个节点的左手子节点小于父节点的值，并且每个节点的右手子节点大于父节点
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class Tree {
constructor() {
this.root = null;
}
isValidBST(node, min = null, max = null) {
if (!node) return true;
if (max !== null && node.data >= max) {
return false;
}
if (min !== null && node.data <= min) {
return false;
}
const leftSide = this.isValidBST(node.left, min, node.data);
const rightSide = this.isValidBST(node.right, node.val, max);
return leftSide && rightSide;
}
}
const t = new Node(10);
t.left = new Node(0);
t.left.left = new Node(7);
t.left.right = new Node(4);
t.right = new Node(12);
const t1 = new Tree();
t1.root = t;
console.log(t1.isValidBST(t));Stack Overflow用户
发布于 2020-03-18 22:56:19
另一种解决方案可以是：
const isValidBST = (
root,
min = Number.MIN_SAFE_INTEGER,
max = Number.MAX_SAFE_INTEGER
) => {
if (root == null) return true;
if (root.val >= max || root.val <= min) return false;
return (
isValidBST(root.left, min, root.val) &&
isValidBST(root.right, root.val, max)
);
};页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34044902
复制相关文章
相似问题