二叉树锯齿形层序遍历

Binary Tree Zigzag Level Order Traversal

个人笔记

问题：二叉树锯齿形层序遍历

考察：树、广度优先搜索、二叉树

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal

Problem: Binary Tree Zigzag Level Order Traversal

Patterns: Tree, Breadth-First Search, Binary Tree

Recency: 6mo

Link: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：按层 BFS。每层收集节点值，根据层号决定正序追加或反转后追加，也可以用双端队列按方向插入。

复杂度：时间 O(n)，空间 O(w)，w 为树的最大宽度。

Approach: Run BFS by levels. For each level, append node values left-to-right or right-to-left depending on the level parity.

Complexity: Time $O(n)$ , space $O(w)$ for maximum width.