用按层次顺序遍历二叉树的方法,统计树中度为1的结点数目
时间: 2023-04-22 19:00:14 浏览: 411
可以使用层次遍历的方法,从根节点开始,依次遍历每一层的节点,统计每一层中度为1的节点数目,最后累加得到整个树中度为1的节点数目。
具体实现方法如下:
1. 定义一个队列,将根节点入队。
2. 循环执行以下步骤,直到队列为空:
a. 取出队首节点,统计其度数。
b. 如果该节点的左子节点不为空,将左子节点入队。
c. 如果该节点的右子节点不为空,将右子节点入队。
3. 统计每一层中度为1的节点数目,累加得到整个树中度为1的节点数目。
代码实现如下:
```python
def count_degree_one(root):
if not root:
return
queue = [root]
count =
while queue:
size = len(queue)
level_count =
for i in range(size):
node = queue.pop()
if node.left:
queue.append(node.left)
level_count += 1
if node.right:
queue.append(node.right)
level_count += 1
count += level_count
return count
```
其中,变量`count`用于累加整个树中度为1的节点数目,变量`level_count`用于统计每一层中度为1的节点数目。在每一层遍历结束后,将`level_count`累加到`count`中。最后返回`count`即可。
阅读全文