统计二叉树叶子结点个数

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

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

6-3 统计二叉树叶子结点个数

题目要求实现一个函数，统计二叉树的叶子结点个数。具体实现方法是遍历二叉树，对于每个节点，如果它是叶子节点，则计数器加1，否则递归遍历它的左右子树。最后返回计数器的值即可。

以下是参考代码：

int LeafCount(BiTree T) {
    int cnt = 0;
    if (T != NULL) {
        cnt += LeafCount(T->lchild); // 左子树的叶子节点个数
        cnt += LeafCount(T->rchild); // 右子树的叶子节点个数
        if (T->lchild == NULL && T->rchild == NULL) // 如果是叶子节点
            cnt++; // 那么就自加一
    }
    return cnt;
}