二叉树的层序遍历
🟡 中等题目描述
给你二叉树的根节点 root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
示例 1
输入：root = [3, 9, 20, null, null, 15, 7]
输出：[[3], [9, 20], [15, 7]]示例 2
输入：root = [1]
输出：[[1]]示例 3
输入：root = []
输出：[]提示
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
解法
参考答案 (3 个标签)
BFS 队列 O(n)
思路
使用队列进行广度优先搜索，每次处理一层的所有节点。
代码实现
/**
* @param {TreeNode} root
* @return {number[][]}
*/
function levelOrder(root) {
if (root === null) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(w)，w 为树的最大宽度
关键点
- 使用
levelSize记录当前层的节点数 - 内层循环只处理当前层的节点
- 新加入的节点属于下一层
解法
参考答案 (3 个标签)
DFS 递归 O(n)
思路
递归时传递当前深度，将节点值添加到对应层的数组中。
代码实现
/**
* @param {TreeNode} root
* @return {number[][]}
*/
function levelOrder(root) {
const result = [];
function dfs(node, depth) {
if (node === null) return;
if (result.length === depth) {
result.push([]);
}
result[depth].push(node.val);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
}
dfs(root, 0);
return result;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(h)