求二叉树第k层节点个数
时间: 2024-08-16 15:06:14 浏览: 52
要计算二叉树第k层的节点数量,可以使用广度优先搜索(BFS)算法。以下是Python的一个实现:
```python
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_nodes_kth_level(root, k):
if not root or (k < 1): return 0
queue = deque([root])
levels = {0: 1} # 初始化每一层的节点数,根节点为第0层
while queue:
level_size = len(queue)
next_level = []
for _ in range(level_size):
node = queue.popleft()
if node.left: next_level.append(node.left)
if node.right: next_level.append(node.right)
if k > 0:
k -= 1
else:
return levels.get(k, 0)
levels[level_size] = len(next_level)
# 示例
# 假设我们有如下的二叉树结构:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
# 则第2层(深度为1,因为根节点是第0层)的节点数为2,调用 `count_nodes_kth_level` 函数,传入根节点和k=2,返回结果应为2。
阅读全文