102. 二叉树的层序遍历

题目链接：102. 二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

核心思考：广度优先搜索 (BFS) 与队列

层序遍历是二叉树 广度优先搜索 (BFS) 最最经典的应用。它需要我们按照从上到下、每一层从左到右的顺序逐个处理。

1. 选择数据结构：广度优先与队列 (Queue) 是绑定的，因为队列能提供先入先出 (FIFO) 的特性，完美贴合我们“一层一层按顺序吐出”的需求。在 Python 中通常使用 collections.deque 高效实现。
2. 分组隔离机制：虽然只是丢入队列，但题目要求按层归类包装成列表（List of Lists）。为此，我们可以在 while q: 循环体内部，再次嵌套一个 for _ in range(len(q))：
   • 因为在这一瞬间，队列里的元素数量 len(q) 恰恰就是当前这一层的所有节点数。
   • 只要把它们批量弹干净，并在弹出的同时把它们的左右子节点压入队尾，就能完美划清每一层之间的界限！

解题思路 (Python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
            
        ans = []
        q = deque([root])
        
        while q:
            cur = []
            # 记录此时队列的长度，即为【当前层】的全部节点数
            for _ in range(len(q)):
                node = q.popleft()
                cur.append(node.val)
                # 将下一层的子节点排入队尾
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(cur)
            
        return ans

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树的节点的数量。对于每一个节点，我们只做一次进队列和一次出队列的操作，时间开销严格与节点总数成正比。
• 空间复杂度：O(N)。在最坏情况下（比如完全二叉树的最后一层），队列中会同时存在整个树的大约一半的节点，所占用的连续最大空间量级为 O(N)。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

val1 val2 val3 ... valN

输入一行整数数组表示二叉树的层序遍历，None 表示空节点。

完整代码：

import sys

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

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    i = 1
    while queue and i < len(arr):
        node = queue.pop(0)
        if arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    return root

def tree_to_list(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if root is None:
                return []

            ans = []
            q = deque([root])

            while q:
                cur = []
                # 记录此时队列的长度，即为【当前层】的全部节点数
                for _ in range(len(q)):
                    node = q.popleft()
                    cur.append(node.val)
                    # 将下一层的子节点排入队尾
                    if node.left:
                        q.append(node.left)
                    if node.right:
                        q.append(node.right)
                ans.append(cur)

            return ans

def main():
    arr = sys.stdin.read().strip().split()
    tree_arr = [None if v == 'None' else int(v) for v in arr]
    root = build_tree(tree_arr)

    sol = Solution()
    result = sol.levelOrder(root)
    print(result)

if __name__ == "__main__":
    main()