编写递归算法计算二叉树中叶子结点的数目
时间: 2024-03-25 17:12:17 浏览: 13
好的,请稍等片刻,让我思考一下。
实际上,计算二叉树中叶子结点的数目可以使用递归算法来解决。具体而言,我们可以通过先遍历左子树和右子树,再将它们的叶子节点数量相加的方式来计算整个二叉树中的叶子节点数量。
以下是递归计算叶子结点的 Python 代码实现:
```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 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)
```
以上代码中,'count_leaves' 函数的参数是二叉树的根节点 'root',它会对输入的树进行递归遍历,让我们来逐个讲解函数中的代码:
1. 如果二叉树为空,则返回 0,因为树中不含任何叶子节点。
```python
if root is None:
return 0
```
2. 如果二叉树不为空,但它的左右子树均为空,则说明它是叶子节点,返回 1。
```python
if root.left is None and root.right is None:
return 1
```
3. 如果该节点既不是叶子节点,也不是空节点,则递归计算该节点的左子树和右子树中叶子节点的数量,并将两部分结果相加。
```python
return count_leaves(root.left) + count_leaves(root.right)
```
这样,就可以通过简单的递归计算,得出二叉树中叶子节点的数量了。