用队列实现二叉树的层序遍历并计算其结点个数和高度
时间: 2023-12-03 20:43:11 浏览: 124
层序遍历-二叉树的存储结构和遍历算法
二叉树的层序遍历可以使用队列来实现,具体方法如下:
1. 将根节点入队列。
2. 当队列不为空时,取出队头元素,即当前层的第一个节点,并将其左右子节点(如果有)入队列。
3. 处理完当前层的所有节点后,计算当前层的节点个数。
4. 重复步骤2和3,直到队列为空。
计算二叉树的节点个数可以使用递归方法,即左子树的节点数加右子树的节点数再加1(根节点),递归到叶子节点时返回0。
计算二叉树的高度也可以使用递归方法,即左子树的高度和右子树的高度中取最大值,再加1(当前节点的高度),递归到叶子节点时返回0。
以下是代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order(root):
if not root:
return 0, 0
queue = [root]
count = 0
height = 0
while queue:
level_size = len(queue)
count += level_size
height += 1
for i in range(level_size):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return count, height
def count_nodes(root):
if not root:
return 0
return count_nodes(root.left) + count_nodes(root.right) + 1
def max_depth(root):
if not root:
return 0
return max(max_depth(root.left), max_depth(root.right)) + 1
```
其中,`level_order`函数返回二叉树的节点个数和高度,`count_nodes`函数计算节点个数,`max_depth`函数计算高度。
阅读全文