层次遍历二叉树

Question

层次遍历二叉树是一种广度优先搜索的方法，它按层次顺序遍历二叉树的节点，从根节点开始，每一层从左到右遍历。具体的实现方法可以借助于队列，步骤如下：

1. 将根节点加入队列。
2. 当队列非空时，重复以下步骤：
   • 弹出队列的队首元素，并访问该节点。
   • 如果该节点有左儿子，将左儿子加入队列。
   • 如果该节点有右儿子，将右儿子加入队列。
3. 遍历完成后，所有节点都被访问过。

以下是一个示例代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root: TreeNode) -> List[List[int]]:
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        level = []
        size = len(queue)
        for i in range(size):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

这个函数接受一个根节点的参数，返回一个二维列表，其中每一行代表一层节点的值。该函数首先创建一个空列表 result 和一个队列 queue ，将根节点加入队列。在循环中，首先弹出队列的队首元素，并将其值加入到当前层的列表 level 中，然后将其左儿子和右儿子加入队列中。在每一次循环结束后，将当前层的列表加入到 result 中，直到队列为空。最后返回 result 列表即可。