企业官网建设流程全解析

LeetCode 102. 二叉树的层序遍历

题目描述

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

示例:

输入: root = [3,9,20,null,null,15,7] 输出: [[3],[9,20],[15,7]] 3 / \ 9 20 / \ 15 7

题解：BFS（广度优先搜索）

核心思路

用队列逐层处理节点。关键在于在每层开始时记录队列长度，这个长度就是当前层的节点数，从而将同一层的节点归到同一个子数组中。

TypeScript 实现

classTreeNode{val:number;left:TreeNode|null;right:TreeNode|null;constructor(val?:number,left?:TreeNode|null,right?:TreeNode|null){this.val=val===undefined?0:val;this.left=left===undefined?null:left;this.right=right===undefined?null:right;}}functionlevelOrder(root:TreeNode|null):number[][]{constresult:number[][]=[];if(root===null)returnresult;constqueue:TreeNode[]=[root];while(queue.length>0){constlevelSize=queue.length;// 当前层的节点数constcurrentLevel:number[]=[];for(leti=0;i<levelSize;i++){constnode=queue.shift()!;// 出队currentLevel.push(node.val);if(node.left)queue.push(node.left);if(node.right)queue.push(node.right);}result.push(currentLevel);}returnresult;}

复杂度分析

指标 复杂度 说明
时间 O(n) 每个节点恰好入队、出队一次
空间 O(n) 队列最多存一层的节点，最坏（完全二叉树叶子层）约 n/2

代码要点说明

1. levelSize 是关键：进入 while 循环时先保存 queue.length，本次循环只处理这 levelSize 个节点，新入队的子节点留给下一轮，从而自然分层。
2. queue.shift() 与性能：JS 数组的 shift() 是 O(n) 操作。若追求更优性能，可用索引指针代替 shift：

functionlevelOrder(root:TreeNode|null):number[][]{constresult:number[][]=[];if(!root)returnresult;constqueue:TreeNode[]=[root];lethead=0;// 队头指针，避免 shift 的 O(n) 开销while(head<queue.length){constlevelSize=queue.length-head;constcurrentLevel:number[]=[];for(leti=0;i<levelSize;i++){constnode=queue[head++];currentLevel.push(node.val);if(node.left)queue.push(node.left);if(node.right)queue.push(node.right);}result.push(currentLevel);}returnresult;}

3. 递归（DFS）写法也可行：用一个 depth 参数标记层级，把节点值 push 到 result[depth] 中，但本题 BFS 更直观。

DFS 递归写法（补充）

functionlevelOrder(root:TreeNode|null):number[][]{constresult:number[][]=[];constdfs=(node:TreeNode|null,depth:number):void=>{if(!node)return;if(!result[depth])result[depth]=[];result[depth].push(node.val);dfs(node.left,depth+1);dfs(node.right,depth+1);};dfs(root,0);returnresult;}