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[][]intifroot==nil{returnres}queue:=[]*TreeNode{root}head:=0// 队头索引，避免频繁切片leftToRight:=trueforhead<len(queue){size:=len(queue)-head// 当前层节点数level:=make([]int,size)fori:=0;i<size;i++{node:=queue[head]head++// 根据方向决定填充位置ifleftToRight{level[i]=node.Val}else{level[size-1-i]=node.Val}// 子节点始终按从左到右入队ifnode.Left!=nil{queue=append(queue,node.Left)}ifnode.Right!=nil{queue=append(queue,node.Right)}}res=append(res,level)leftToRight=!leftToRight// 切换方向}returnres}复杂度分析
指标 复杂度 说明
时间 O(n) 每个节点恰好入队、出队一次，填充 level 为 O(1)
空间 O(n) 队列最多存一层的节点，最坏约 n/2；结果集存储所有节点值
关键点说明
- 用 head 索引代替 queue = queue[1:]：避免频繁切片带来的额外开销，同时减少底层数组的内存保留问题。
- 固定子节点入队顺序：无论当前层方向如何，都先 Left 后 Right 入队，保证下一层在队列中始终是从左到右排列。
- 方向交替：每层结束后 leftToRight = !leftToRight，实现锯齿效果。
- 空树处理：root == nil 时直接返回空切片。
替代写法（先收集再反转）
如果不想用索引定位，也可以正常追加后再按需反转：
forhead<len(queue){size:=len(queue)-head level:=make([]int,0,size)fori:=0;i<size;i++{node:=queue[head]head++level=append(level,node.Val)ifnode.Left!=nil{queue=append(queue,node.Left)}ifnode.Right!=nil{queue=append(queue,node.Right)}}if!leftToRight{forl,r:=0,len(level)-1;l<r;l,r=l+1,r-1{level[l],level[r]=level[r],level[l]}}res=append(res,level)leftToRight=!leftToRight}两种写法时间复杂度均为 O(n)，可根据偏好选择。
