二叉树的叶子结点

统计叶子节点数量与收集叶子节点值的方法

一、引言

在计算机科学中，二叉树是一种常见的数据结构，叶子节点指的是没有子节点的节点。在很多算法和问题中，统计叶子节点的数量和收集叶子节点的值是非常关键的步骤。将介绍两种方法来统计叶子节点的数量以及收集叶子节点的值，分别是递归方法和迭代方法。

二、统计叶子节点数量

（一）递归方法

在递归方法中，我们从根节点开始遍历二叉树。如果当前节点为空，返回0；如果当前节点既没有左子节点也没有右子节点，说明是叶子节点，返回1；否则，递归地遍历左子树和右子树，并将结果相加。递归方法的Python代码实现如上所示。

（二）迭代方法（层次遍历）

迭代方法通常使用队列或栈来实现。我们从根节点开始，将其加入队列。然后，在队列非空的情况下，不断取出队首节点，检查其左右子节点。如果节点没有左右子节点，说明是叶子节点，计数器加一。然后，将节点的左右子节点（如果存在）加入队列。迭代方法的Python代码实现也如上所示。

三、收集叶子节点的值

（一）递归方法

在递归方法中，我们同样从根节点开始遍历二叉树。当遇到没有左右子节点的节点时，将其值加入到结果列表中。递归地遍历左子树和右子树，以完成前序遍历。递归方法的Python代码实现如上所示。

（二）迭代方法（前序遍历）

迭代方法的前序遍历需要使用栈来实现。我们从根节点开始，将其加入栈。然后，在栈非空的情况下，不断取出栈顶节点，检查其左右子节点。如果节点没有左右子节点，将其值加入到结果列表中。将右子节点先入栈，左子节点后入栈，以保证前序遍历的顺序。迭代方法的Python代码实现如上所示。

四、复杂度分析

无论是递归方法还是迭代方法，时间复杂度均为O(n)，其中n为二叉树的节点数量，因为每个节点都会被访问一次。空间复杂度方面，递归方法为O(h)，h为树的高度；迭代方法为O(n)，在最坏情况下，队列或栈需要存储所有节点。

五、示例

以一个简单的二叉树为例，该树的叶子节点为4、5、3，数量为3。使用迭代方法的层次遍历或前序遍历，可以收集到的叶子节点值分别为[4, 5, 3]（层次遍历顺序）或[4, 5, 3]（前序遍历顺序）。这些方法能够灵活应对不同结构的二叉树，包括空树、单节点树等特殊情况。

介绍了统计叶子节点数量和收集叶子节点值的两种常用方法：递归方法和迭代方法。这些方法在处理二叉树时具有广泛的应用，能够处理不同结构的二叉树，包括特殊情况下的情况。在实际应用中，可以根据具体需求和场景选择合适的方法。