递归统计二叉树节点数的时间复杂度略高于O(n)，该说法是否正确？

结论 #

你的推导存在问题，属于对时间复杂度计数逻辑和大O表示法规则的误解，该算法的时间复杂度就是O(n)，不需要额外叠加叶子节点的调用开销。

代码示例 #

def count_nodes(node: Node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

详细说明 #

1. 你观察到的「叶子节点会触发两次空节点递归调用并返回0」的现象是对的，但你把这部分开销剥离到O(n)之外的逻辑不成立：
   如果我们定义n为二叉树的非空节点总数，根据二叉树的固有性质，任意n个非空节点的二叉树，空指针的数量固定为n+1，这些空指针对应的就是所有传入None的递归调用。整个算法的总递归调用次数 = 非空节点调用次数n + 空节点调用次数(n+1) = 2n+1，你提到的叶子节点的两次空调用已经包含在这个总数里，不需要额外叠加。
2. 哪怕忽略计数逻辑的问题，你的写法也不符合大O表示法的使用规则：大O表示法只会保留最高阶的项，并且忽略常数系数。就算你硬要把叶子节点的开销单独计算，一棵满二叉树的叶子节点数最多为(n+1)/2，乘以2之后也只有n+1，和前面的O(n)相加之后最高阶项仍然是n，最终结果还是O(n)，不会改变复杂度量级。

内容的提问来源于stack exchange，提问作者Vitor de oliveira