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

Question

在Cracking the Coding Interview第6版中,有一个问题(4.4),你想要找出二叉树是否平衡,在这种情况下平衡意味着任何一方比另一方更深一个以上.

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

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.

在本书的答案部分,作者写了关于这种解决方案的以下内容:

虽然这有效,但效率不高.在每个节点上,我们通过它的整个子树进行递归.这意味着在相同的节点上重复调用getHeight.该算法是O(N log N),因为每个节点在其上方的每个节点被"触摸"一次.

书籍解决方案如下:

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

让我们写出isBalancedas 的时间复杂度函数T(n).因此,平均情况下的递归关系是:

当O(n)来自两个电话来getHeight,这是我们知道的是O(n).因此,使用Master定理,总体复杂度isBalanced是O(n log n).

您的解决方案不会调用isBalanced子节点,这意味着O(n)上面的关系中的一个被替换为a 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).