统计二叉树的叶子结点个数

好的，这是一个经典的二叉树问题。统计二叉树的叶子结点个数可以通过递归实现。具体思路是，如果当前节点为空，则返回0；如果当前节点是叶子节点，则返回1；否则，递归计算左子树和右子树的叶子节点个数，然后将它们相加即可。

以下是 Python 代码实现：

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

def count_leaves(root: TreeNode) -> int:
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

相关问题

统计二叉树叶子结点个数

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

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 是二叉树的高度，这是由于递归调用的栈空间。