求二叉树中的结点个数、叶子结点个数、某结点层次和二叉树宽度

### 计算二叉树中的结点个数

为了计算二叉树中的结点个数，可以采用递归的方式遍历整棵树。对于每一个访问到的结点，增加计数值直到遍历结束。

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

此方法通过递增方式累加每个被访问过的节点数目从而得出总数[^1]。

### 输出二叉树b的叶子结点个数

针对获取叶子结点的数量，则需特别注意那些既无左孩子也无右孩子的结点。每当遇到这样的结点时便将其计入最终的结果之中。

def count_leafs(root):
    if root is None:
        return 0
    elif root.left is None and root.right is None:
        return 1
    else:
        return count_leafs(root.left) + count_leafs(root.right)

上述代码实现了当检测到当前处理的是叶节点（即左右子节点皆为空），则返回1；反之继续向下一层探索直至完成整个树形结构扫描[^2]。

### 求二叉树b中指定结点值的结点的层次

寻找给定值所在层的位置可以通过广度优先搜索(BFS)，因为BFS能够按照从上至下的顺序逐级检查各层内的所有元素。一旦发现目标对象立即停止并记录下此时所处层数作为答案输出。

from collections import deque

def find_node_level(root, target_val):
    queue = deque([(root, 1)])
    
    while queue:
        node, level = queue.popleft()
        
        if not node:
            continue
            
        if node.val == target_val:
            return level
        
        queue.append((node.left, level + 1))
        queue.append((node.right, level + 1))

    return -1  # 如果找不到该节点，则返回-1表示不存在

这段逻辑利用队列辅助存储待考察的对象及其对应的高度信息，在每次迭代过程中更新这些数据以便于后续操作。

### 利用层次遍历求二叉树b的宽度

最大宽度指的是同一水平线上最多含有的非空结点数量。因此同样适用基于队列实现的层次遍历策略，并在此基础上维护一个变量用于跟踪每一轮次的最大长度变化情况。

def max_width(root):
    if not root:
        return 0
    
    width = 0
    queue = [(root, 0)]  # (node, index)

    current_index = 0
    leftmost_index = 0
    rightmost_index = 0
    
    while queue:
        next_queue = []
        for item in queue:
            node, idx = item
            if node.left:
                next_queue.append((node.left, idx*2))
            if node.right:
                next_queue.append((node.right, idx*2+1))
                
        if next_queue:
            leftmost_index = next_queue[0][1]
            rightmost_index = next_queue[-1][1]

        width = max(width, rightmost_index - leftmost_index + 1)
        queue = next_queue[:]
            
    return width

这里采用了稍微不同的做法——不仅保存了节点本身还附加了一个索引来帮助确定最左侧和最右侧位置之间的距离差值，进而得到每一行的实际跨度大小。