DeepSeek LeetCode 103. 二叉树的锯齿形层序遍历 Golang实现

LeetCode 103. 二叉树的锯齿形层序遍历 Golang 实现思路与普通层序遍历一致用队列逐层处理。区别在于需要交替改变每层的填充方向· 维护布尔变量 leftToRight 表示当前层方向。· 每层预分配 level : make([]int, size)· 从左到右level[i] node.Val· 从右到左level[size-1-i] node.Val· 子节点始终按 左 → 右 顺序入队保证下一层在队列中从左到右排列。· 每层结束后切换方向。Golang 代码packagemain// Definition for a binary tree node.typeTreeNodestruct{ValintLeft*TreeNode Right*TreeNode}funczigzagLevelOrder(root*TreeNode)[][]int{varres[][]intifrootnil{returnres}queue:[]*TreeNode{root}head:0// 队头索引避免频繁切片leftToRight:trueforheadlen(queue){size:len(queue)-head// 当前层节点数level:make([]int,size)fori:0;isize;i{node:queue[head]head// 根据方向决定填充位置ifleftToRight{level[i]node.Val}else{level[size-1-i]node.Val}// 子节点始终按从左到右入队ifnode.Left!nil{queueappend(queue,node.Left)}ifnode.Right!nil{queueappend(queue,node.Right)}}resappend(res,level)leftToRight!leftToRight// 切换方向}returnres}复杂度分析指标 复杂度 说明时间 O(n) 每个节点恰好入队、出队一次填充 level 为 O(1)空间 O(n) 队列最多存一层的节点最坏约 n/2结果集存储所有节点值关键点说明用 head 索引代替 queue queue[1:]避免频繁切片带来的额外开销同时减少底层数组的内存保留问题。固定子节点入队顺序无论当前层方向如何都先 Left 后 Right 入队保证下一层在队列中始终是从左到右排列。方向交替每层结束后 leftToRight !leftToRight实现锯齿效果。空树处理root nil 时直接返回空切片。替代写法先收集再反转如果不想用索引定位也可以正常追加后再按需反转forheadlen(queue){size:len(queue)-head level:make([]int,0,size)fori:0;isize;i{node:queue[head]headlevelappend(level,node.Val)ifnode.Left!nil{queueappend(queue,node.Left)}ifnode.Right!nil{queueappend(queue,node.Right)}}if!leftToRight{forl,r:0,len(level)-1;lr;l,rl1,r-1{level[l],level[r]level[r],level[l]}}resappend(res,level)leftToRight!leftToRight}两种写法时间复杂度均为 O(n)可根据偏好选择。