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

Question

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

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

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

helper :

def get_height(root):
    if root is None:
        return 0
    else:
        return max(get_height(root.left), get_height(root.right)) + 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 递归访问其下的子树。对于根，get_height 几乎访问了整棵树:N-1 次操作，所以 O(N)。对于根的 2 个 child 中的每一个，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 检查的顺序。对于两个测试最终都通过的任何树，处理总量(因此大 O 效率)不变。

另外，您的逻辑不会检查平衡二叉树:您可能需要重新阅读定义。