实现一个二叉树的层序遍历。

Question

实现一个二叉树的层序遍历。

Accepted Answer

二叉树的层序遍历可以使用广度优先搜索（BFS）的方法来实现。具体思路是使用一个队列来存储待遍历的节点。首先将根节点入队，然后循环从队列中取出节点，访问该节点，并将其左右子节点（如果存在）入队。为了区分不同的层，可以在每一层遍历之前记录当前队列的长度，遍历完当前层的所有节点后再进行下一层的遍历。以下是实现代码：
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 levelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(current_level)
    return result

这种方法的时间复杂度是 O(n)，因为需要遍历二叉树的所有节点；空间复杂度是 O(n)，主要用于存储队列中的节点。