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

LeetCode 103. 二叉树的锯齿形层序遍历 Python3 实现思路与普通层序遍历相同使用队列逐层处理。区别在于需要交替改变每层的遍历方向· 维护布尔变量 left_to_right 表示当前层方向。· 每层用一个 deque 收集节点值· 从左到右append· 从右到左appendleft· 这样无需最后 reverse直接得到正确顺序。Python3 代码fromcollectionsimportdequefromtypingimportOptional,List# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defzigzagLevelOrder(self,root:Optional[TreeNode])-List[List[int]]:ifnotroot:return[]res[]qdeque([root])left_to_rightTruewhileq:level_sizelen(q)leveldeque()for_inrange(level_size):nodeq.popleft()# 根据方向决定插入到尾部还是头部ifleft_to_right:level.append(node.val)else:level.appendleft(node.val)# 子节点始终按从左到右的顺序入队ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)res.append(list(level))left_to_rightnotleft_to_right# 切换方向returnres复杂度分析指标 复杂度 说明时间 O(n) 每个节点恰好入队、出队一次append/appendleft 均为 O(1)空间 O(n) 队列最多存一层的节点最坏约 n/2结果集存储所有节点值关键点说明双端队列的优势collections.deque 的 append 与 appendleft 都是 O(1)避免额外 reverse 操作。子节点入队顺序固定无论当前层方向如何都先 left 后 right 入队保证下一层在队列中始终是从左到右排列。方向交替每层处理完后 left_to_right not left_to_right实现锯齿效果。空树处理root 为空时直接返回空列表。替代写法list reverse如果不想用双端队列也可以正常添加后再按需反转whileq:level_sizelen(q)level[]for_inrange(level_size):nodeq.popleft()level.append(node.val)ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)ifnotleft_to_right:level.reverse()res.append(level)left_to_rightnotleft_to_right两种写法时间复杂度均为 O(n)可根据偏好选择。