以二叉链表作为二叉树的存储结构,编写以下算法: 统计二叉树的叶结点个数的编码、
时间: 2024-01-23 08:08:27 浏览: 93
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
以下是统计二叉树叶结点个数的算法的Python代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_leaf_nodes(root):
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)
# 测试代码
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(count_leaf_nodes(root)) # 输出 4
```
该算法的思路是,如果当前节点是空节点,那么返回0;如果当前节点是叶子节点(即左右子节点都为空),那么返回1;否则递归计算左右子树的叶子节点数量之和。时间复杂度为 $O(n)$,其中 $n$ 是二叉树的节点数。
阅读全文