当前位置：首页 > article >正文

统计二叉树叶子结点个数

article 2025/1/31 13:56:56

以下为你介绍统计二叉树叶子结点个数的常见方法，包括递归和非递归两种实现方式，并以代码示例（以Python为例）来说明：

递归方法

思路：
- 对于一棵二叉树，其叶子结点是指没有左子树和右子树的结点。
- 可以通过递归遍历二叉树来统计叶子结点个数。递归计算左子树的叶子结点个数、右子树的叶子结点个数，然后判断根结点是否为叶子结点（即左子树和右子树都为空），如果是则加上1 。
代码示例：

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


def count_leaf_nodes(root):
    if root is None:
        return 0
    # 递归计算左子树叶子结点个数
    left_leaf_count = count_leaf_nodes(root.left)
    # 递归计算右子树叶子结点个数
    right_leaf_count = count_leaf_nodes(root.right)
    # 如果根结点是叶子结点，返回左子树叶子结点个数 + 右子树叶子结点个数 + 1
    if root.left is None and root.right is None:
        return left_leaf_count + right_leaf_count + 1
    # 否则返回左子树叶子结点个数 + 右子树叶子结点个数
    return left_leaf_count + right_leaf_count

在上述代码中：

首先定义了二叉树的节点类 TreeNode。
然后 count_leaf_nodes 函数实现了统计叶子结点个数的功能。通过对根结点及其左右子树的递归处理，最终返回整棵二叉树的叶子结点个数。

非递归方法（利用队列实现层次遍历）

思路：
- 利用队列进行层次遍历二叉树。
- 在遍历过程中，当一个结点的左子树和右子树都为空时，就说明该结点是叶子结点，此时计数加1 。
代码示例：

from collections import deque


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


def count_leaf_nodes_non_recursive(root):
    if root is None:
        return 0
    leaf_count = 0
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node.left is None and node.right is None:
            leaf_count += 1
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return leaf_count