如何计算非平衡二叉树给定深度的节点数量

不存在脱离树实际结构的通用闭式公式可以直接计算任意非平衡二叉树指定深度的节点数。完美二叉树的2^d公式成立前提是所有非叶子节点都恰好拥有2个子节点，一旦出现节点缺失子节点的情况，节点数就完全由每一层实际存在节点的子节点分布决定，只能基于上一层的节点状态逐层递推得到精确结果。

核心递推规则 #

计数逻辑非常简单，没有特殊例外：

• 根节点所在层的节点数固定为1（深度计数起点可自行约定，不影响逻辑）
• 任意深度k的节点总数 = 深度k-1层所有节点拥有的左子节点总数 + 右子节点总数

对应你举的例子：根节点（深度0，共1个节点）只有1个子节点，深度1的节点数就是1；如果深度1的节点有2个子节点，深度2的节点数就是2；如果某层上的所有节点加起来只生出8个子节点，那下一层节点数就是8，和满二叉树预期的16个节点没有必然关联。

注意：如果只需要估算值，可以基于历史层的平均子节点数做预测，但要得到精确值没有任何捷径——哪怕上一层有100个节点，只要99个节点没有子节点、剩下1个节点有2个子节点，下一层就只有2个节点，不存在通用的比例系数可以套用。

广度优先搜索（BFS）迭代实现 #

这是该问题的最优实现方案，按层遍历树，不会访问目标深度以下的节点，时间复杂度为从根到目标深度的所有节点总数，代码如下（Python实现）：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_nodes_at_depth(root: TreeNode, target_depth: int) -> int:
    # 空树直接返回0
    if not root:
        return 0
    # 初始化：当前在根节点层，深度记为0
    current_level_nodes = [root]
    current_depth = 0

    while current_level_nodes:
        # 到达目标深度，直接返回当前层节点数
        if current_depth == target_depth:
            return len(current_level_nodes)
        # 收集下一层所有存在的子节点
        next_level_nodes = []
        for node in current_level_nodes:
            if node.left:
                next_level_nodes.append(node.left)
            if node.right:
                next_level_nodes.append(node.right)
        # 进入下一层
        current_level_nodes = next_level_nodes
        current_depth += 1
    # 遍历完树仍未到达目标深度，说明目标深度超出树的最大深度，返回0
    return 0

小提示：如果你习惯根节点为深度1的计数规则，只需要把初始current_depth设为1即可，核心逻辑不需要改动。

无实体树结构的纯计数递推方法 #

如果你不需要遍历实际树节点，手上已经有每一层节点的子节点存在标记，可以直接用纯计数的方式递推，不需要构建树结构：

def cal_next_layer_count(prev_layer_child_flags: list[tuple[bool, bool]]) -> int:
    """
    参数说明：prev_layer_child_flags 是上一层每个节点的子节点存在标记
    每个元素为二元组，格式为(左子节点是否存在, 右子节点是否存在)
    返回值：下一层的精确节点数
    """
    total = 0
    for has_left, has_right in prev_layer_child_flags:
        total += int(has_left) + int(has_right)
    return total

要计算深度为d的节点数，只需要从根节点的子节点标记开始，连续调用这个函数d次，就能逐层算出目标层的节点数，额外开销极低。

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