检查二叉搜索树是否有效 javascript

Question

我在网上遇到了这个问题，我发现了以下函数来检查 BST 是否有效。但是，我不完全理解最大/最小如何从空更改为可以比较的值。所以在下面的函数中：

//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 更改为其他值...当我进行控制台时，我在控制台中得到了这个。记录每次运行的最小值/最大值。

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

Answer 1

该变量min变为非空，因为您显式调用

isValidBST(node.right, node.val, max)

您将 node.val 作为 param 传递的位置min。必须是在您进行此调用时node.val不为空；