统计二叉树的叶节点个数
时间: 2024-08-14 11:04:23 浏览: 32
统计二叉树的叶节点个数通常涉及到遍历二叉树的过程。在一棵二叉树中,叶节点是没有孩子的节点,即左孩子为空且右孩子也为空的节点。有几种常见的算法可以计算二叉树的叶节点数:
1. **递归法**:从根节点开始,如果当前节点是叶节点(`null`左右子节点),则计数加一;然后递归地对左右子树进行同样的操作。最终返回的结果就是叶节点总数。
```python
def count_leaves(root):
if root is None:
return 0
elif root.left is None and root.right is None: # 当前节点是叶子节点
return 1
else:
return count_leaves(root.left) + count_leaves(root.right)
```
2. **迭代法**:可以使用栈来辅助遍历,依次将非叶节点的左右子节点压入栈,遇到叶节点时计数加一,并同时弹出所有父节点直到到达根节点。
```python
def count_leaves_iterative(root):
stack, count = [root], 0
while stack:
node = stack.pop()
if not node.left and not node.right: # 叶节点
count += 1
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return count
```
无论哪种方法,关键在于理解二叉树的结构和遍历策略。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)