1. 问题描述

给定一棵二叉树，要求计算其叶子结点的个数。叶子结点是指没有子结点的结点。

2. 递归求解

最直接的方法是使用递归来解决这个问题。对于一个二叉树结点，如果它没有子结点，则它是一个叶子结点，计数为 1。否则，它的叶子结点个数等于其左右子树的叶子结点个数之和。

```python

def count_leaves(root):

if root is None:

return 0

if root.left is None and root.right is None:

return 1

else:

return count_leaves(root.left) + count_leaves(root.right)

```

3. 迭代求解

除了递归之外，我们还可以使用迭代的方法来求解这个问题。我们可以使用层次遍历（也称为广度优先搜索）来遍历二叉树。在遍历过程中，我们遇到一个没有子结点的结点时，就将叶子结点计数加 1。

```python

def count_leaves_iterative(root):

queue = [root]

leaves = 0

while queue:

node = queue.pop(0)

if node.left is None and node.right is None:

leaves += 1

else:

if node.left is not None:

queue.append(node.left)

if node.right is not None:

queue.append(node.right)

return leaves

```

4. 两种方法的时间复杂度

递归和迭代方法的时间复杂度都是 O(n)，其中 n 是二叉树中的结点个数。这是因为两种方法都需要遍历二叉树中的每个结点。

5. 空间复杂度

递归方法的空间复杂度为 O(h)，其中 h 是二叉树的高度。这是因为递归调用需要在栈中存储函数调用。

迭代方法的空间复杂度为 O(w)，其中 w 是二叉树中每一层的最大宽度。这是因为层次遍历需要在队列中存储每一层的结点。

6. 实现

以下是用 Python 实现的递归和迭代算法：

```python

递归

def count_leaves(root):

if root is None:

return 0

if root.left is None and root.right is None:

return 1

else:

return count_leaves(root.left) + count_leaves(root.right)

迭代

def count_leaves_iterative(root):

if root is None:

return 0

queue = [root]

leaves = 0

while queue:

node = queue.pop(0)

if node.left is None and node.right is None:

leaves += 1

else:

if node.left is not None:

queue.append(node.left)

if node.right is not None:

queue.append(node.right)

return leaves

```

7. 总结

求二叉树叶子结点的个数是一个常见的面试问题。有两种主要方法可以解决这个问题：递归和迭代。两种方法的时间复杂度都是 O(n)，但空间复杂度有所不同。递归方法的空间复杂度为 O(h)，而迭代方法的空间复杂度为 O(w)。