.jpg)
555 字
3 分钟
二叉树的层序遍历
题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
解题思路
叉树的层次遍历解题思路
- 队列辅助：
- 使用队列（FIFO）存储待访问节点
- 初始将根节点入队
- 分层处理：
- 记录当前层节点数（队列长度）
- 遍历当前层所有节点，访问值并存入结果
- 子节点入队：
- 将当前节点的左/右子节点（非空）加入队列
- 迭代推进：
- 完成一层后推进到下一层
- 队列为空时终止
关键洞察
- 队列核心作用：
- 队列保证先进先出，实现层级顺序访问
- 队首始终是当前层最左侧节点
- 层尺寸记录：
- 每层开始前记录队列长度 = 当前层节点数
- 确保精准分层收集结果
- 空值优化：
- 跳过空子节点不入队，减少无效操作
- 空间效率：
- 队列最大尺寸不超过最宽层节点数
- 完美树时空间复杂度最低
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：每个节点进出队列各一次 |
| 空间复杂度 | O(w)：w为树最大宽度（队列存储节点数不超过最宽层节点数） |
注：n为节点总数，w为二叉树最大宽度（叶子最多的一层）
代码实现
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[][]} */var levelOrder = function (root) {
if(!root) return [];
const result = [] const queue = [root] while (queue.length) { const item = [] const size = queue.length for (let i = 0; i < size; i++) { const node = queue.pop() item.push(node.val) if (node.left) queue.unshift(node.left) if (node.right) queue.unshift(node.right) } result.push(item) } return result};