102. 二叉树的层序遍历
题目描述
输入二叉树的根节点 root。按层把节点值收集起来：先是根所在的第一层，再往下一层一层处理。
每一层内部按从左往右的次序排列节点值，组成一个列表。返回所有层的列表，层的顺序从上到下。
树用层序数组表示，null 代表空位。空树返回空列表 []。
示例 1
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
解释：三层分别是 [3]、[9,20]、[15,7]。
示例 2
输入：root = [1] 输出：[[1]]
解释：只有根节点一层。
示例 3
输入：root = [] 输出：[]
解释：空树没有任何层。
数据范围
- 节点总数在
[0, 2000]之间。 -1000 <= Node.val <= 1000
解题思路：广度优先搜索
队列做广度优先搜索；每轮先固定当前队列长度，只处理这一层。
为什么正确
每轮开始时队列恰好包含当前层的节点，顺序从左到右。
复杂度分析
时间 O(n)，辅助队列 O(w)，输出 O(n)，w 为最大层宽。
易错点
不能边遍历队列边按动态长度决定本层范围，必须固定层大小。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from collections import deque
class Solution:
def levelOrder(self, root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultclass Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null)
return new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>(List.of(root));
List<List<Integer>> result = new ArrayList<>();
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
result.add(level);
}
return result;
}
}class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root)
return {};
queue<TreeNode*> q({root});
vector<vector<int>> result;
while (!q.empty()) {
vector<int> level;
for (int i = q.size(); i > 0; i--) {
TreeNode* node = q.front(); q.pop();
level.push_back(node->val);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
result.push_back(level);
}
return result;
}
};func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
queue := []*TreeNode{root}
result := [][]int{}
for len(queue) > 0 {
level := []int{}
for range len(queue) {
node := queue[0]; queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}var levelOrder = function(root) {
if (!root)
return [];
const queue = [root];
const result = [];
while (queue.length) {
const level = [];
for (let i = queue.length; i > 0; i--) {
const node = queue.shift();
level.push(node.val);
if (node.left)
queue.push(node.left);
if (node.right)
queue.push(node.right);
}
result.push(level);
}
return result;
};function levelOrder(root: TreeNode | null): number[][] {
if (!root)
return [];
const queue: TreeNode[] = [root];
const result: number[][] = [];
while (queue.length) {
const level: number[] = [];
for (let i = queue.length; i > 0; i--) {
const node = queue.shift()!;
level.push(node.val);
if (node.left)
queue.push(node.left);
if (node.right)
queue.push(node.right);
}
result.push(level);
}
return result;
};其他解法
广度优先搜索按层推进，最直观；深度优先搜索靠 depth 参数把节点放进对应层，空间随树高而不是层宽变化。
解法 2：深度优先搜索 时间 O(n)，空间 O(h)
递归时带上当前深度 depth。第一次到达某个深度时，在结果里新建一层。按先左后右的顺序递归，把节点值追加到第 depth 层末尾，同层顺序自然是从左到右。
辅助空间取决于树高 h 而不是层宽 w，宽而矮的树更省空间。深链树递归很深，Python 需要调高递归深度。
import sys
class Solution:
def levelOrder(self, root):
sys.setrecursionlimit(10000)
result = []
def dfs(node, depth):
if not node:
return
if depth == len(result):
result.append([])
result[depth].append(node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root, 0)
return resultclass Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
dfs(root, 0, result);
return result;
}
private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
if (node == null) return;
if (depth == result.size()) result.add(new ArrayList<>());
result.get(depth).add(node.val);
dfs(node.left, depth + 1, result);
dfs(node.right, depth + 1, result);
}
}class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
dfs(root, 0, result);
return result;
}
void dfs(TreeNode* node, int depth, vector<vector<int>>& result) {
if (!node) return;
if (depth == (int)result.size()) result.push_back({});
result[depth].push_back(node->val);
dfs(node->left, depth + 1, result);
dfs(node->right, depth + 1, result);
}
};func levelOrder(root *TreeNode) [][]int {
result := [][]int{}
var dfs func(node *TreeNode, depth int)
dfs = func(node *TreeNode, depth int) {
if node == nil {
return
}
if depth == len(result) {
result = append(result, []int{})
}
result[depth] = append(result[depth], node.Val)
dfs(node.Left, depth+1)
dfs(node.Right, depth+1)
}
dfs(root, 0)
return result
}var levelOrder = function(root) {
const result = [];
const dfs = (node, depth) => {
if (!node) return;
if (depth === result.length) result.push([]);
result[depth].push(node.val);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
};
dfs(root, 0);
return result;
};function levelOrder(root: TreeNode | null): number[][] {
const result: number[][] = [];
const dfs = (node: TreeNode | null, depth: number): void => {
if (!node) return;
if (depth === result.length) result.push([]);
result[depth].push(node.val);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
};
dfs(root, 0);
return result;
};