检查二进制搜索树是否为有效javascript
Checking if a Binary Search Tree is Valid javascript
我在网上遇到了这个问题,我发现了以下函数来检查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 min/max时,我都会在控制台中得到这个。
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
给定一个节点,验证二进制搜索树,确保每个节点的左手子节点小于父节点的值,并且每个节点的右侧子节点都大于父
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));
由于显式调用,变量min
变为非null
isValidBST(node.right, node.val, max)
其中您将node.val作为参数min
传递。必须是,在您进行此调用时,node.val
不是null;
另一种解决方案可能是:
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)
);
};
检查二进制搜索树是否有效:
class BTNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
/**
*
* @param {BTNode} tree
* @returns {Boolean}
*/
const isBinarySearchTree = (tree) => {
if (tree) {
if (
tree.left &&
(tree.left.value > tree.value || !isBinarySearchTree(tree.left))
) {
return false;
}
if (
tree.right &&
(tree.right.value <= tree.value || !isBinarySearchTree(tree.right))
) {
return false;
}
}
return true;
};
相关文章:
- Javascript袖珍参考,第121页:这是怎么回事;猴子补丁”;方法应该有效
- 什么'是在asp.net MVC中将本地化的resources.resx文件转换为javascript文件的有效
- Rails将JavaScript对象存储到Model的有效方式
- Javascript XMLHttpRequest——只有第一个POST请求有效
- 外部链接的Javascript文件赢得't执行,但函数有效
- 如何有效地创建多维javascript数组
- Javascript/Ajax:通过点击按钮检查有效的电子邮件和电话号码
- 如何在javascript中将字符串转换为有效日期
- javascript/jQuery:在title中添加换行符——在IE9中有效,但在IE8中无效
- 将javascript数组中的项移动到特定位置的有效方法
- Javascript:字符串中有效的基于数组的替换
- Javascript下载在firefox中停止,但在Chrome中有效
- slack files.upload-如何从javascript/jQuery将文件作为有效负载发送
- 跨浏览器的有效 JavaScript 名称
- 使用具有有效 JavaScript 格式的 Json.NET 序列化对象
- 我的开关结构似乎有效(JavaScript 控制结构)
- 检查二进制搜索树是否为有效javascript
- Typescript字典编码的有效Javascript字典函数到类
- 我必须遵循什么规则来编写没有分号的有效Javascript ?
- 使用对象文字表示法创建对象的有效Javascript语法是什么?