二叉树的叶子结点个数
时间: 2023-12-17 19:27:30 浏览: 42
二叉树的叶子结点是指没有子节点的节点,因此计算二叉树的叶子结点个数需要遍历整棵树并统计叶子结点的数量。可以使用递归或迭代的方式实现遍历,以下是两种常见的实现方式:
1. 递归实现
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_leaf_nodes(root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
```
2. 迭代实现
```python
def count_leaf_nodes(root: TreeNode) -> int:
if not root:
return 0
stack = [root]
count = 0
while stack:
node = stack.pop()
if not node.left and not node.right:
count += 1
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return count
```