验证二进制搜索树-JavaScript

validating a Binary Search Tree - JavaScript

本文关键字:-JavaScript 搜索树 二进制 验证      更新时间:2023-09-26

我正在尝试编写一个验证二进制搜索树的函数。我有一个版本可以按顺序遍历并推送到数组,但我也在尝试做一个版本,递归地跟踪最小值和最大值。我成功地传入了树,它检查了我的第一个checkBST函数中的第一个节点,但在isValidBST函数里,递归调用从未发生过,似乎每个节点都被视为null,我不知道为什么。将感谢任何人的投入!

function BinarySearchTree(value) {
  this.val = value;
  this.left = null;
  this.right = null;
}
//insert
BinarySearchTree.prototype.insert = function (toInsert) {
  if (this.val > toInsert) {
    if (this.left === null) {
      this.left = new BinarySearchTree(toInsert);
    } else {
      this.left.insert(toInsert);
    }
  }
  if (this.val < toInsert) {
    if (this.right === null) {
      this.right = new BinarySearchTree(toInsert);
    } else {
      this.right.insert(toInsert);
    }
  }
};

function checkBST(node) {
  // console.log(node.right);
  return isValidBST(node, null, null);
}
function isValidBST(node, min, max) {
  // console.log(min, max);
  //this keeps getting called
  if (node === null) {
    console.log("CHECKING NULL");
    return true;
  }
  // this doesn't get called, which is good 
  if ((min !== null && node.val > max) || (max !== null && node.val < min)) {
    console.log("CHECKING NODE VALUES in false", node.val);
    return false;
  }
  //these calls are never entered.
  if (!checkBST(node.left, min, node.val) || !checkBST(node.right, node.val, max)) {
    console.log("CHECKING NODE VALUES in recursive call", node.val);
    return false;
  }
  return true;
}

var bst = new BinarySearchTree(7);
bst.insert(9);
bst.insert(6);
bst.insert(4);

console.log(checkBST(bst));

当前代码中有一个容易错过但很重要的缺陷:isValidBST()应该递归到自身中(isValidBSC()),而不是递归到忽略节点参数后的任何参数的checkBST(。