完全二叉树节点计数解法的时间复杂度疑问

题目描述 #

给定一棵完全二叉树的根节点root，返回树的节点总数。
根据维基百科定义，完全二叉树除最后一层外所有层都完全填满，最后一层节点尽可能靠左，该层ℎ的节点数在1到2^ℎ之间（包含边界值）。
请设计时间复杂度低于O(n)的算法。

我的实现代码 #

def countNodes(self, root: Optional[TreeNode]) -> int:
    if not root: return 0
    def maxDepth(root):
        # this finds the maximum depth of the tree 
        # it goes down just the left side of the tree, where nodes are guaranteed
        # O(d) - depth of left-side
        if not root:
            return -1

        return 1 + maxDepth(root.left)


    d = maxDepth(root)
    def dfs(root, depth):
        if not root:
            return 0
        if depth == d:
            # if we've reached the bottom nodes, return 1 (counting itself)
            return 1
        
        left, right = 0, 0
        left = dfs(root.left, depth + 1)
        if left == ((2 ** (d - depth)) // 2):
            # determine if we must go to the right (halve the problem)
            # depends on how many bottom nodes are returned by the left recursion
            # for instance, if the depth of the tree is 4 (start from 0), and 
            # the current depth is 2, then this subtree should have 4 bottom nodes
            # if it doesn't, the parent does not have to recurse rightward
            right = dfs(root.right, depth + 1)
        
        return left + right

    bottom = dfs(root, 0)
    top = (2 ** (d)) - 1
    return top + bottom

我的疑问 #

我不确定dfs(root, depth)函数中的判断逻辑是否能降低时间复杂度，担心底层节点全满的最坏情况下时间复杂度仍为O(n)，此时每次都会调用dfs(root.right, depth + 1)，希望得到解答。

解答 #

你的担心是多余的，这个算法的时间复杂度确实是O(log²n)，远低于O(n)，理由如下：

1. 树深度计算的时间开销：maxDepth函数仅遍历左子树，时间复杂度为O(d)，其中d是树的深度。对于完全二叉树，节点数n满足2^d ≤ n < 2^(d+1)，因此d等价于log₂n。

2. dfs递归的次数分析：

   • 即使底层节点全满，每次递归左子树都会返回预期的节点数，触发右子树递归，但每一层的递归最多访问两个节点（左、右子节点）。
   • 递归的总次数是d + (d-1) + ... + 1 = O(d²)，代入d=log₂n后，时间复杂度就是O(log²n)。对比O(n)的全遍历，当n为10^6时，log²n仅约为400，效率差距显著。

3. 判断逻辑的有效性：

   • (2 ** (d - depth)) // 2代表当前节点左子树应包含的底层节点数。如果左子树返回的节点数等于该值，说明左子树底层已满，必须递归右子树统计；反之则右子树底层无节点，无需递归。
   • 这个判断确保了我们不会遍历所有底层节点，而是通过分治思想逐步缩小统计范围，仅在必要时访问右子树。

综上，即便在底层全满的最坏场景下，算法的时间复杂度仍为O(log²n)，完全满足题目要求的低于O(n)的时间复杂度。

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