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.valvalundefined?0:val;this.leftleftundefined?null:left;this.rightrightundefined?null:right;}}functionlevelOrder(root:TreeNode|null):number[][]{constresult:number[][][];if(rootnull)returnresult;constqueue:TreeNode[][root];while(queue.length0){constlevelSizequeue.length;// 当前层的节点数constcurrentLevel:number[][];for(leti0;ilevelSize;i){constnodequeue.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代码要点说明levelSize 是关键进入 while 循环时先保存 queue.length本次循环只处理这 levelSize 个节点新入队的子节点留给下一轮从而自然分层。queue.shift() 与性能JS 数组的 shift() 是 O(n) 操作。若追求更优性能可用索引指针代替 shiftfunctionlevelOrder(root:TreeNode|null):number[][]{constresult:number[][][];if(!root)returnresult;constqueue:TreeNode[][root];lethead0;// 队头指针避免 shift 的 O(n) 开销while(headqueue.length){constlevelSizequeue.length-head;constcurrentLevel:number[][];for(leti0;ilevelSize;i){constnodequeue[head];currentLevel.push(node.val);if(node.left)queue.push(node.left);if(node.right)queue.push(node.right);}result.push(currentLevel);}returnresult;}递归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,depth1);dfs(node.right,depth1);};dfs(root,0);returnresult;}
