algorithm - 找出二叉树是否平衡的大O(来自CTCI Book)

Question

在 Cracking the Coding Interview 第 6 版中有一个问题 (4.4)，您应该在其中找出二叉树是否平衡，在这种情况下平衡意味着任何一侧是否比另一侧深超过 1。

我这样递归地解决了这个问题:

def isBalanced(root):
  return abs(getDepth(root.left) - getDepth(root.right)) > 1

def getDepth(node):
  if node is None:
    return 0
  return 1 + max([getDepth(node.left), getDepth(node.right)])

所以要遍历它。它递归地检查每个节点的每一侧并将其向上传递给根，如果根的左右子树之间的差异大于 1，则返回 False，否则返回 True。

在本书的答案部分，作者写了以下关于此类解决方案的内容:

Although this works, it's not very efficient. On each node, we recurse through it's entire subtree. This means that getHeight is called repeatedly on the same nodes. The algorithm is O(N log N) since each node is "touched" once per node above it.

书籍解决方案如下:

int getHeight(TreeNode root) {
  if (root == null) return -1;
  return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

boolean isBalanced(TreeNode root) {
  if (root == null) return true;

  int heightDiff = getHeight(root.left) - getHeight(root.right);
  if (Math.abs(heightDiff) < 1) {
    return false;
  } else {
    return isBalanced(root.left) && isBalanced(root.right);
  }
}

不幸的是，我不明白这是怎么回事。在我看来，该算法只检查它下面的级别。每个节点都未检查多次。当我看这个算法时，它是 O(N)。

谁能帮我确认一下我是否正确理解了这个算法的 Big-O，或者我是否遗漏了什么？

Answer 1

让我们将isBalanced 的时间复杂度函数写成T(n)。因此，平均案例递归关系是:

其中 O(n) 来自对 getHeight 的两次调用，我们知道这是 O(n)。因此，使用 Master 定理，isBalanced 的整体复杂度为 O(n log n)。

您的解决方案没有在子节点上调用 isBalanced，这意味着上面关系中的 O(n) 被替换为 O(1) ，总体上给出 O(n)(同样来自 Master 定理)。然而，它并没有(作为一个明显的结果!)检查子节点是否平衡，所以是不正确的。

CTCI 天真的解决方案的问题是它有效地为每个子节点再次调用getHeight(通过调用isBalanced)，这是不必要的.可以将平衡检查功能合并到 getHeight 中以获得 O(n) 中的解决方案:

int balance_internal(TreeNode root)
{
    // change the specification slightly to return 0 for a leaf
    // ... and -1 for an unbalanced node
    if (root == null) return 0;

    int left_h = balance_internal(root.left);
    int right_h = balance_internal(root.right);

    // if either node is unbalanced
    if (left_h == -1 || right_h == -1)
        return -1;

    // return max height as before
    // ... but now with the knowledge that both child nodes are balanced
    return Math.abs(left_h - right_h) > 1 ? -1 : 1 + Math.max(left_h, right_h);
}

boolean isBalanced(TreeNode root)
{
    return (balance_internal(root) > -1);
}

虽然可能不像提供的解决方案那样优雅，但这不会创建对子节点的重复调用，而是重用第一组调用的结果。因此，递归关系与您自己的解决方案相同，给出 O(n)。