以二叉链表作为二叉树的存储结构，假设二叉树中每个结点的值为单 个字符，设计算法：统计二叉树中叶结点的个数。

在二叉链表表示的二叉树中，可以采用递归的方式来统计叶节点的数量。叶节点是指没有左右子节点的节点。以下是算法的设计步骤：

1. **基本情况**：
- 如果当前节点为空，则返回0，因为没有节点；
- 如果当前节点是一个叶节点（即左孩子和右孩子都为空），则返回1。

2. **递归情况**：
- 继续对当前节点的左子节点调用递归函数，累加结果；
- 再对当前节点的右子节点调用递归函数，累加结果；
- 将两次的结果相加，得到当前节点所在的子树中叶节点的总数，然后加上1（当前节点本身也是一个叶节点）。

以下是Python伪代码实现：

def count_leaves(root):
    if root is None:
        return 0
    elif not (root.left or root.right):  # 判断是否为叶节点
        return 1
    else:
        left_count = count_leaves(root.left) if root.left else 0
        right_count = count_leaves(root.right) if root.right else 0
        return left_count + right_count + 1  # 当前节点自身也是叶节点

# 调用函数，并传入二叉树的根节点
leaf_count = count_leaves(root_of_binary_tree)

相关问题

以二叉链表作为二叉树的存储结构，编写交换二叉树每个结点的左孩子和右孩子的算法

假设二叉树的二叉链表存储结构如下所示：

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

可以使用递归的方式来实现交换二叉树的每个结点的左孩子和右孩子。具体的实现过程如下：

def swapTree(root: TreeNode) -> TreeNode:
    if not root:
        return None
    
    # 交换左右孩子
    root.left, root.right = root.right, root.left
    
    # 递归处理左右子树
    swapTree(root.left)
    swapTree(root.right)
    
    return root

在上面的代码中，我们首先交换当前结点的左右孩子，然后递归处理左右子树。最后返回根节点即可。

数据结构以二叉链表作为二叉树的存储结构统计二叉树的叶结点个数

数据结构中的二叉链表作为一种常见的二叉树存储结构，用于表示二叉树的节点和它们之间的连接。对于统计二叉树的叶结点（即没有子节点的节点），你可以按照以下步骤操作：

1. 遍历二叉链表：从根节点开始，使用深度优先搜索（DFS）或广度优先搜索（BFS）的方式遍历整棵树。因为每个非叶子节点最多有两个子节点，所以到达叶节点时无需进一步访问。

2. 记录计数：每当遇到一个叶节点（判断节点是否只有一个指向空的指针），就将叶结点的数量加一。

3. 终止条件：在遍历过程中，当整个二叉链表都检查完毕，记录的叶结点数量就是所求。

以下是使用递归的示例算法（假设`Node`是一个包含左右子节点引用的二叉链表节点类）：

def count_leaves(root):
    if not root:  # 如果当前节点为空，则返回0
        return 0
    elif not root.left and not root.right:  # 如果当前节点是叶子节点
        return 1
    else:
        left_count = count_leaves(root.left)  # 递归计算左子树的叶节点数
        right_count = count_leaves(root.right)  # 递归计算右子树的叶节点数
        return left_count + right_count  # 返回两部分叶节点之和

# 使用时传入二叉链表的根节点
leaf_count = count_leaves(root)