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

Question

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

3

我正在练习一些面试题，尝试确定给定二叉树是否平衡的时间复杂度。

我认为解决方案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

- Liondancer

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tony Delroy · Accepted Answer

我认为解决方案2的时间复杂度为O(n)，而解决方案1的时间复杂度为O(n^2)。

我认为不是这样的，如下所述。

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

这并不简单。假设您在根上调用is_balanced()：因为它递归地访问树中的每个节点，它调用get_height，该函数递归访问下面的子树。对于根，get_height几乎访问整个树：N-1次操作，因此O(N)。对于根节点的两个子节点，get_height访问其（大约）一半的树：同样是O(N)。直到get_height在N/2个叶节点下的~N个None节点上运行：仍然是O(N)。总之，在树中有~log2N级别，您在每个级别上都做了O(N)处理，因此整体复杂度为O(NlogN)。

解决方案2比较高度的事实意味着随着我们向树的顶部移动，我们无需返回检查子树的高度。

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

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