LeetCode 题解工作台
二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 示例 1： 输入： root = [3,9,20,null,null,15,7] 输出： [[3],[20,9],[15,7]] 示例 2： 输入： root…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
为了实现锯齿形层序遍历，需要在层序遍历的基础上增加一个标志位 `left`，用于标记当前层的节点值的顺序。如果 `left` 为 `true`，则当前层的节点值按照从左到右的顺序存入结果数组 `ans` 中；如果 `left` 为 `false`，则当前层的节点值按照从右到左的顺序存入结果数组 `ans` 中。 时间复杂度 ，空间复杂度 。其中 为二叉树的节点数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -100 <= Node.val <= 100
解题思路
方法一：BFS
为了实现锯齿形层序遍历，需要在层序遍历的基础上增加一个标志位 left，用于标记当前层的节点值的顺序。如果 left 为 true，则当前层的节点值按照从左到右的顺序存入结果数组 ans 中；如果 left 为 false，则当前层的节点值按照从右到左的顺序存入结果数组 ans 中。
时间复杂度 ，空间复杂度 。其中 为二叉树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root])
ans = []
left = 1
while q:
t = []
for _ in range(len(q)):
node = q.popleft()
t.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(t if left else t[::-1])
left ^= 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you maintain the current level direction while traversing nodes to ensure proper zigzag order?
- question_mark
Can you optimize the reversal step to avoid creating new lists unnecessarily at each level?
- question_mark
Will you handle edge cases such as empty trees or single-node trees correctly?
常见陷阱
外企场景- error
Forgetting to reverse the node values at every alternate level, resulting in standard level order output instead of zigzag.
- error
Using a standard queue without managing insertion direction, which forces costly list reversals each time and increases overhead.
- error
Incorrectly indexing levels during recursion or BFS, causing misplacement of node values and breaking the zigzag pattern.
进阶变体
外企场景- arrow_right_alt
Binary Tree Level Order Traversal without zigzag reversal, focusing solely on left-to-right BFS grouping per level.
- arrow_right_alt
Spiral Order Traversal of a binary tree with two stacks, an alternative DFS-based method to achieve zigzag order.
- arrow_right_alt
Bottom-Up Zigzag Level Order Traversal where the traversal starts from leaves to root, requiring reversed collection after BFS.