此代码是否准确确定二叉搜索树是否平衡？

Question

我知道我可以只看一些例子，但我花了很长时间自己尝试得到这个，我想知道我是否成功了。它通过了我给它的测试，但我可以对代码进行健全性检查吗？

每个节点都是一个 javascript class，左右属性等于另一个节点或未定义。我还为 Node class 编写了一个 .hasChildren() 方法，它的功能听起来很像。

这个函数是我的 BinaryTree class 的一个方法，它有另一个方法 .height() 接受任何节点并确定从该节点开始的树的高度。这里是 .isBalanced() 方法，它也需要一个节点开始：

BinaryTree.prototype.isBalanced = function (node = this.root) {
    const rBalanced = (node) => {
    // a node with no children is balanced
    if (!node.hasChildren()) {
      return true
    }

    // get the difference in heights between the branches, using -1 for a missing child
    const left = node.left ? this.height(node.left) : -1
    const right = node.right ? this.height(node.right) : -1

    // if the difference is 1 or less, this node is balanced
    const balanced = Math.abs(left - right) <= 1

    // ensure that every child tree, if it exists, is also balanced
    if (node.left && !node.right) {
      return balanced && rBalanced(node.left)
    }
    if (!node.left && node.right) {
      return balanced && rBalanced(node.right)
    }
    return balanced && rBalanced(node.left) && rBalanced(node.right)
    }
  // a nonexistent tree is balanced (???)
  return node ? rBalanced(node) : true
}

这里是 .height() 方法以防万一：

BinaryTree.prototype.height = function (node = this.root) {
    const rHeight = (node, count) => {
        return Math.max(
            count,
            node.left ? rHeight(node.left, count + 1) : null,
            node.right ? rHeight(node.right, count + 1) : null
        )
    }
    return node ? rHeight(node, 1) : 0
}

编辑：这是一个带有工作代码的 jsfiddle https://jsfiddle.net/jonahsaltzman/u2jrosLm/

Answer 1

函数isBalanced是正确的，但是height函数有一个不一致的地方，导致isBalancedreturn的结果是错误的。例如对于这棵树，它 returns false，但是 true 是预期的：

      2
     /
    1

height中的问题是return在没有节点的情况下为0。但是在 isBalanced 中，您在这种情况下使用 -1。比较从每个函数中获取的这两个表达式：

node ? rHeight(node, 1) : 0

和：

node.left ? this.height(node.left) : -1

这不一致。 non-existing 节点的高度为 -1 或高度为 0，但此处您混合了两者。由于标准是将空树视为高度为 -1，因此更改 height:

中的代码

node ? rHeight(node, 0) : -1
//                  ^^    ^^

此代码是否准确确定二叉搜索树是否平衡？

Does this code accurately determine if a binary search tree is balanced?

javascript

algorithm

binary-tree

binary-search-tree