JavaScript； validateBinaryTree 函数在节点上给出值错误

Question

这是一项编码挑战，我们将编写一个函数来确定二叉树是否有效。该树只是手动链接在一起的 BinaryTreeNode 的集合。如果左子树上的任何值大于根值，则 validateBinaryTree 函数应返回 false；如果右子树上的任何值小于根值，则函数应返回 false，否则返回 true。

这是BinaryTreeNode 类:

class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insertLeft(value) {
    this.left = new BinaryTreeNode(value);
    return this.left;
  }

  insertRight(value) {
    this.right = new BinaryTreeNode(value);
    return this.right;
  }

  depth_first_print() {
    console.log(this.value);
    if (this.left) {
      this.left.depth_first_print();
    }
    if (this.right) {
      this.right.depth_first_print();
    }
  }

}

这是validateBinaryTree函数:

const validateBinaryTree = (rootNode) => {
  const rootValue = rootNode.value;
  let isValid = true;
  const validateLeft = (node) => {
    if (node.value > rootValue) isValid = false;
    if (node.left) {
      validateLeft(node.left);
    }
    if (node.right) {
      validateLeft(node.right);
    }
  }
  const validateRight = (node) => {
    if (node.value < rootValue) isValid = false;
    if (node.left) {
      validateRight(node.left);
    }
    if (node.right) {
      validateRight(node.right);
    }
  }
  validateLeft(rootNode.left);
  validateRight(rootNode.right);
  return isValid;
}


//Build an invalid binary tree which will look like this:
//    10
//   /
//  50

const tree = new BinaryTreeNode(10);
tree.insertLeft(50);

以下函数调用应将 false 打印到控制台:

console.log(validateBinaryTree(tree));

但是我收到以下错误:

if (node.value < rootValue) isValid = false;
             ^

TypeError: Cannot read property 'value' of null

Answer 1

您的初始代码失败，因为您尝试在 rootNode.right 上调用 validateRight，该值是 null。这就是为什么实际上最好将该检查(针对 node === null 情况)放置在验证器本身内部。

此外，我还通过在内部传递两个单独的函数来简化此代码 - 一个用于左分支，另一个用于右分支 - 根据 rootNode 值关闭。例如:

const validateBinaryTree = (rootNode) => {
  const forLeft  = val => val < rootNode.value;
  const forRight = val => val > rootNode.value;

  const validateBranch = (node, branchComparator) => {
    return node === null || 
      branchComparator(node.value) &&
      validateBranch(node.left, branchComparator) && 
      validateBranch(node.right, branchComparator);
  }

  return validateBranch(rootNode.left, forLeft) && validateBranch(rootNode.right, forRight);
}

这个版本还有一个(轻微的)好处，只要发现失败的节点就立即停止检查(因为 JS 中 && 运算符的短路性质)。