我在线上遇到了这个问题,然后我找到了下面的函数来检查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 时)。不知何故,最小值从 null 变为了 1,我没有看到具体原因,我认为你需要一些基本情况才能使最小值从 null 变为其他值......
每次运行时,如果在控制台上输出 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
if (!isValidBST(node.left, min, node.val) || !isValidBST(node.right, node.val, max)) {
- bhspencerisValidBST(node.right, node.val, max)
,所以 node.val 不能为空。 - bhspencer