统计二叉树叶子节点个数

统计二叉树的叶子节点（即没有子节点的节点）个数通常可以通过递归的方式实现。对于任何给定的二叉树：

1. 如果根节点为空，那么叶子节点个数就是0。
2. 否则，如果根节点有左子节点和右子节点，我们需要分别计算左子树和右子树的叶子节点个数，然后将两者相加，得到的结果再加上根节点本身（因为它是叶子节点）。

这是一个典型的递归过程，每次函数调用都会检查当前节点是否为叶子节点，如果是就增加计数，然后对左右子节点进行同样的操作，直到遍历完整棵树。

如果你需要具体的算法代码实现，可以参考以下伪代码：

def count_leaves(root):
    if root is None:  # 判断节点是否为空
        return 0
    elif root.left is None and root.right is None:  # 检查是否为叶子节点
        return 1
    else:
        left_count = count_leaves(root.left)  # 递归计算左子树叶子节点
        right_count = count_leaves(root.right)
        return left_count + right_count  # 返回叶子节点总数

相关问题

统计二叉树叶子结点个数

统计二叉树叶子结点个数的方法是通过递归实现的。具体步骤如下：

1. 如果当前节点为空，则返回0。
2. 如果当前节点没有左右子节点，则返回1。
3. 否则，递归计算左子树和右子树的叶子结点个数，并将它们相加。

以下是示例代码：

int countLeafNodes(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

2．利用递归算法实现对二叉树的先序遍历、统计二叉树结点个数、计算二叉树的深度、统计二叉树单孩子结点个数、统计二叉树叶子结点个数。

好的,我很乐意为您介绍如何使用递归算法实现二叉树的各种操作。下面我将逐一介绍先序遍历、统计节点个数、计算深度、统计单孩子节点个数和统计叶子节点个数的递归实现方法:

1. 先序遍历:

def preorder_traversal(root):
    if root is None:
        return
    print(root.val)  # 访问根节点
    preorder_traversal(root.left)  # 遍历左子树
    preorder_traversal(root.right)  # 遍历右子树

2. 统计二叉树节点个数:

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

3. 计算二叉树的深度:

def tree_depth(root):
    if root is None:
        return 0
    left_depth = tree_depth(root.left)
    right_depth = tree_depth(root.right)
    return max(left_depth, right_depth) + 1

4. 统计单孩子节点个数:

def count_single_child(root):
    if root is None or (root.left is None and root.right is None):
        return 0
    count = 0
    if root.left is None or root.right is None:
        count += 1
    count += count_single_child(root.left) + count_single_child(root.right)
    return count

5. 统计叶子节点个数:

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

这些递归函数都遵循了相似的模式:
1. 首先处理基本情况(通常是节点为空的情况)
2. 然后处理当前节点
3. 最后递归处理左右子树

这些方法的时间复杂度都是 O(n)，其中 n 是二叉树的节点数，因为每个节点都会被访问一次。空间复杂度在最坏情况下是 O(h)，其中 h 是二叉树的高度，这是由于递归调用的栈空间。