二叉树平衡性判断算法的空间复杂度分析咨询

先看你提供的判断二叉树是否平衡的代码：

def height(t):
    if t is None:
        return 0

    return max(height(t.left), height(t.right)) + 1

def is_balanced_binary_tree(tree: BinaryTreeNode) -> bool:
    if tree is None:
        return True

    if abs(height(tree.left) - height(tree.right)) > 1:
        return False
    
    return is_balanced_binary_tree(tree.left) and is_balanced_binary_tree(tree.right)

时间复杂度 #

你提到的O(NlogN)是平衡二叉树场景下的时间复杂度：

• 对于高度为H=logN的平衡二叉树，每个节点都会被height函数访问，且每层节点对应的height调用会遍历其下所有子节点。累计下来，每个节点被访问的次数和它所在的层数相关，整体时间复杂度为O(NlogN)。
• 如果是完全倾斜的二叉树（比如链表结构），高度H=N，此时时间复杂度会退化为O(N²)，因为每个节点的height调用都会遍历后续所有节点。

空间复杂度 #

你对函数调用次数和空间复杂度的关联理解有误，空间复杂度的核心是递归调用栈的最大深度，而非总调用次数——因为递归栈是后进先出的结构，函数执行完成后对应的栈帧会立即释放，同一时间内存中只存在当前递归路径上的栈帧。

具体分析这个算法的空间复杂度：

• 首先，height函数的递归栈深度等于树的高度H，比如计算根节点左子树高度时，递归栈会从根左节点一直延伸到最底层叶子节点，深度为H。
• 然后，is_balanced_binary_tree的递归栈深度同样是H，递归遍历左、右子树时，栈深度最多达到当前子树的高度。
• 关键是这些调用都是串行执行的：先计算左子树高度（栈深度H），执行完栈释放；再计算右子树高度（栈深度H），执行完栈释放；接着递归判断左子树是否平衡（栈深度H-1），执行完栈释放，再处理右子树。整个过程中，递归栈的最大深度始终是H。

所以这个算法的空间复杂度是O(H)，其中H是树的高度。对于平衡二叉树，H=logN，空间复杂度为O(logN)；对于倾斜树，H=N，空间复杂度为O(N)。

你提到的“遍历N个节点时空间复杂度为4HN”是错误的，总调用次数不决定空间复杂度，只需要看同一时间内存中存在的最大栈帧数量即可。

内容的提问来源于stack exchange，提问作者quercus1234