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

Question

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

这里是 BinaryTreeNode class:

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 中 && 运算符的短路特性）。

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

JavaScript; validateBinaryTree function gives value error on node

javascript

validation

recursion

binary-tree