[二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/description/) ## 题目描述 给你二叉树的根节点 root，返回其节点值的层序遍历结果。（即逐层地，从左到右访问所有节点）。 层序遍历的定义：按照树的层次，从上到下、从左到右依次访问每个节点。 **示例** ```text 输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]] 3 / \ 9 20 / \ 15 7 ``` ```text 输入：root = [1] 输出：[[1]] ``` ```text 输入：root = [] 输出：[] ``` ## 解题思路 核心思想是：使用队列（Queue）进行广度优先搜索（BFS）。 ```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 from collections import deque; class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] q = deque( [ root ] ) values = [] while q: size = len( q ) t = [] for i in range( 0, size ): node = q.popleft() t.append( node.val ) if node.left: q.append( node.left ) if node.right: q.append( node.right ) values.append( t ) return values ``` **时间复杂度: `O(n)`** **空间复杂度: `O(w)`** n = 节点总数 w = 树的最大宽度 ( 最坏情况`O(n)` )