检查二叉树是否平衡的时间复杂度

Question

我正在练习一些面试题，我试图计算出我的解决方案的时间复杂度以确定给定的二叉树是否平衡。

我认为解决方案 2 的时间复杂度为 O(n)，而解决方案 1 的时间复杂度为 O(n^2)。这是因为在解决方案 1 中，您向下递归到树的底部以检查树是否平衡并检查子树高度的差异。额外的复杂性随着我们向树的根向上移动而变得更高，get_height 仍然向下递归树以计算高度。因此，再次沿着树向下移动 --> O(n^2)。

解决方案 2 首先比较高度，这意味着当我们向上移动树时，我们不必向下移动来检查子树高度。

帮手：

def get_height(root):
    if root is None:
        return 0
    else:
        return max(get_height(root.left), get_height(root.right)) + 1

解决方案 1：

def is_balanced(root):
    if root is None:
        return True
    else:
        return is_balanced(root.right) and is_balanced(root.left) and (abs(get_height(root.left) - get_height(root.right)) < 2)

解决方案 2：

def is_balanced2(root):
    if root is None:
        return True
    else:
        return (abs(get_height(root.left) - get_height(root.right)) < 2) and is_balanced(root.right) and is_balanced(root.left)

检查时差的代码：

s = time.time()
print("result: {}".format(is_balanced(a)))
print("time: {}".format(time.time() - s))

s = time.time()
print("result: {}".format(is_balanced2(a)))
print("time: {}".format(time.time() - s))

不平衡树的结果：

result: False
time: 2.90870666504e-05    # solution 1
result: False
time: 1.50203704834e-05    # solution 2

Answer 1

I believe that solution 2 has a time complexity of O(n) while solution 1 has a time complexity of O(n^2).

我不这么认为，如下所述。

...in solution 1, you recurse down to the bottom of the tree to check if the tree is balanced and also check for differences in subtree height. The extra complexity comes as we go higher back up the tree towards the root, the get_height still recurses down the tree to compute the height. Therefore, traveling down the tree once more --> O(n^2).

没那么简单。假设您在根上调用 is_balanced()：当它递归访问树中的每个节点时，它调用 get_height 递归访问 sub-tree there-under。对于根，get_height 几乎访问了整棵树：N-1 次操作，所以 O(N)。对于每个根的 2 children，get_height 访问它们（大约）一半的树：同样是 O(N)。这一直持续到 get_height 在 N/2 叶节点下的 ~N None 个节点上运行：仍然是 O(N)。总的来说，树中有 ~log2N 层，你对每个层进行 O(N) 处理，所以整体复杂度为 O(NlogN)。

The fact that solution 2 compares the height first, means that as we move back up the tree, we dont have to go back down to check the subtree height.

没有。您在解决方案二中所做的更改是执行 is_balanced 与 get_height 检查的顺序。对于两个测试最终都通过的任何树，处理总量（因此 big-O 效率）不变。

另外，您的逻辑不检查平衡二叉树：您可能需要 re-read 定义。

检查二叉树是否平衡的时间复杂度

Time complexity of checking if a binary tree is balanced

python

algorithm

tree