以二叉链表作为二叉树的存储结构,编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2023-06-16 10:02:07 浏览: 40
下面是用Python实现的代码:
```python
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrderTraversal(root):
if not root:
return []
queue = [root]
res = []
while queue:
node = queue.pop(0)
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
def countDegreeOneNodes(root):
if not root:
return 0
queue = [root]
count = 0
while queue:
node = queue.pop(0)
if (node.left and not node.right) or (node.right and not node.left):
count += 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return count
# 测试
root = TreeNode(1, TreeNode(2, TreeNode(4), None), TreeNode(3, None, TreeNode(5)))
print(levelOrderTraversal(root)) # [1, 2, 3, 4, 5]
print(countDegreeOneNodes(root)) # 2
```
首先定义一个`TreeNode`类表示二叉树的结点,包括值`val`、左子节点`left`和右子节点`right`。然后实现用层次顺序遍历二叉树的方法`levelOrderTraversal`,使用一个队列来遍历二叉树,先将根节点入队,然后每次从队列中取出一个节点,将其值加入结果列表中,然后依次将其左右子节点入队,直到队列为空。最后实现统计树中度为1的结点个数的方法`countDegreeOneNodes`,同样使用一个队列来遍历二叉树,如果一个节点有左子节点但没有右子节点,或者有右子节点但没有左子节点,说明这个节点的度为1,统计个数即可。