二叉树锯齿形层序遍历
Binary Tree Zigzag Level Order Traversal
题目详情
问题：二叉树锯齿形层序遍历
考察：树、图
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/binary-tree-zigzag-level-order-traversal/
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
解析
思路：按层 BFS。每层收集节点值，根据层号决定正序追加或反转后追加，也可以用双端队列按方向插入。
复杂度：时间 O(n)，空间 O(w)，w 为树的最大宽度。