找出二叉树是否平衡的大O（来自CTCI书） [英] Big O of finding out if a binary tree is balanced (From CTCI Book)

问题描述

在《破解编码访谈第六版》中，有一个问题（4.4），您在这里想找出一棵二叉树是否平衡，在这种情况下，平衡是指任一侧的深度是否比另一侧深1倍以上。

In Cracking the Coding Interview 6th Edition there's a question (4.4) where you're suppose to find out if a binary tree is balanced, where balanced in this case means if any side is deeper than the other by more than 1.

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

I solved this recursively like this:

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。

So to walk through it. It recursively check each side of each node and pass it up to the root, if the root then have a higher difference between the left and right subtrees than 1, it returns False, else True.

在本书的答案部分中，作者针对这种类型的解决方案写了以下内容：

In the answer section of the book the author writes the following about this type of solution:

尽管可以，但是不太有效。在每个节点上，我们遍历整个子树。这意味着getHeight在相同的节点上被重复调用。该算法为O（N log N），因为每个节点都在其上方的每个节点接触一次。

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.

books解决方案是以下：

The books solution is the following:

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）。

Unfortunately I can't understand how this is the case. In my mind, the algorithm only checks the level below it. Each node is not checked multiple times. When I look at this algorithm it is O(N).

有人可以帮我确认我是否正确理解了该算法的Big-O或是否错过了一些事情？

Can someone help me confirm if I understood the Big-O of this algorithm correctly, or if I missed something?

推荐答案

让我们将 isBalanced 的时间复杂度函数写为 T（n）。因此，平均情况下的递归关系为：

Let's write the time complexity function of isBalanced as T(n). The average-case recurrence relation is therefore:

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

Where the O(n) comes from the two calls to getHeight, which we know to be O(n). Therefore, using the Master theorem, the overall complexity of isBalanced is O(n log n).

您的解决方案不会在子节点上调用 isBalanced ，这意味着 O（n）替换为 O（1），总体上得到 O（n） （同样是来自母定理）。但是，它并不会（显然是后果！）检查子节点是否平衡，因此是不正确的。

Your solution does not call isBalanced on the child nodes, which means the O(n) in the relation above is replaced by an O(1), giving O(n) overall (again from the Master theorem). It does not however (as an obvious consequence!) check that the child nodes are balanced, so is incorrect.

CTCI天真的解决方案的问题在于它有效地调用了<再次为每个子节点code> getHeight （通过调用 isBalanced ），这是不必要的。可以将余额检查功能合并到 getHeight 中，以获取 O（n）中的解决方案：

The problem with CTCI's naive solution is that it effectively calls getHeight again for each child node (by calling isBalanced), which is unnecessary. One can incorporate the balance-checking functionality into getHeight to obtain a solution in 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）。

Although perhaps not as graceful as the provided solution, this does not create duplicate calls to child nodes, and instead reuses the results from the first set of calls. The recurrence relation is thus the same as that of your own solution, giving O(n).

这篇关于找出二叉树是否平衡的大O（来自CTCI书）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！