0103. Binary Tree Zigzag Level Order Traversal
==============================================
题目信息
--------
:题号: 0103. 二叉树的锯齿形层序遍历
:难度: Medium
:主题: 二叉树、广度优先搜索、队列、下标映射
:原题: `LeetCode 0103 `_
:重点: 分离节点发现顺序与行内输出顺序,再把奇数层反转压缩为目标下标映射
题目重述
--------
给定二叉树根节点 ``root``,逐层返回所有节点值,但相邻层的行内方向必须交替:深度 ``0`` 从左到右,
深度 ``1`` 从右到左,深度 ``2`` 再从左到右,依此类推。
每个深度单独形成一个子数组,结果只包含实际存在的节点,不为空孩子保留占位。空树返回空数组;遍历过程
不修改树。
树中节点总数在 ``0..2000`` 范围内,节点值在 ``-100..100`` 范围内。
自建示例
--------
* 多层稀疏树:``root = [8,4,12,2,6,10,14,null,3]``,返回
``[[8],[12,4],[2,6,10,14],[3]]``;
* 反向层含缺口:``root = [1,2,3,null,5,null,7]``,返回 ``[[1],[3,2],[5,7]]``。第二层反向输出,
第三层恢复从左到右,空孩子不占位置;
* 单节点:``root = [9]``,返回 ``[[9]]``,方向切换不会产生额外空行;
* 空树:``root = []``,返回 ``[]``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
#include
class Solution {
private:
std::vector> collectThenReverse(TreeNode* root) {
if (!root) {
return {};
}
std::vector> levels;
std::queue pending;
pending.push(root);
bool leftToRight = true;
while (!pending.empty()) {
const int levelSize = static_cast(pending.size());
std::vector level;
level.reserve(levelSize);
for (int count = 0; count < levelSize; ++count) {
TreeNode* node = pending.front();
pending.pop();
level.push_back(node->val);
if (node->left) {
pending.push(node->left);
}
if (node->right) {
pending.push(node->right);
}
}
if (!leftToRight) {
std::reverse(level.begin(), level.end());
}
levels.push_back(std::move(level));
leftToRight = !leftToRight;
}
return levels;
}
std::vector> writeToTargetPositions(TreeNode* root) {
if (!root) {
return {};
}
std::vector> levels;
std::queue pending;
pending.push(root);
bool leftToRight = true;
while (!pending.empty()) {
const int levelSize = static_cast(pending.size());
std::vector level(levelSize);
for (int index = 0; index < levelSize; ++index) {
TreeNode* node = pending.front();
pending.pop();
const int targetIndex = leftToRight ? index : levelSize - 1 - index;
level[targetIndex] = node->val;
if (node->left) {
pending.push(node->left);
}
if (node->right) {
pending.push(node->right);
}
}
levels.push_back(std::move(level));
leftToRight = !leftToRight;
}
return levels;
}
public:
std::vector> zigzagLevelOrder(TreeNode* root) {
return writeToTargetPositions(root);
}
};
题解
----
两个顺序
~~~~~~~~
锯齿形要求同时处理两个不同的顺序:先确定哪些节点属于当前层,再决定这些节点在当前行中的排列方向。
前者是节点发现顺序,后者是结果写入顺序。若把两者混在一起,反向层很容易破坏下一层的自然位置关系。
例如根的左右孩子为 ``4``、``12``。深度 ``1`` 应输出 ``[12,4]``,但深度 ``2`` 仍要先考虑 ``4`` 的
孩子,再考虑 ``12`` 的孩子。当前行从右向左展示,不表示下一层也应先从右侧父节点扩展。
因此搜索空间仍按普通层序遍历划分:队列始终保存尚未处理的最浅节点,每轮固定当前层大小,父节点从左到右
出队,每个父节点也始终先加入左孩子、再加入右孩子。锯齿方向只作用于当前行,不作用于树的扩展顺序。
先收集再反转
~~~~~~~~~~~~
最直接的正确方案是先生成普通层序结果,再把深度为奇数的行反转。``collectThenReverse`` 将这两个阶段合并到
同一次 BFS 中:每层先按队列顺序写入 ``level``,若 ``leftToRight`` 为假,再反转整行。
这个方案不会漏节点。层大小快照保证一行只接收同一深度的节点;普通 BFS 保证反转前的顺序为从左到右;
对整行反转恰好得到从右到左。方向状态在整行完成后才切换,因此同一层内不会处理中途改变规则。
瓶颈不是渐进复杂度:所有被反转的行合计也只有不超过 ``n`` 个元素,时间仍为 ``O(n)``。多出的工作是
奇数层先按错误的最终方向写一遍,再扫描并交换一遍。题目已经告诉我们当前层的目标方向,可以在首次写入时
直接放到最终位置。
目标下标映射
~~~~~~~~~~~~
队列按从左到右的自然顺序弹出当前层节点。设层大小为 ``levelSize``,当前弹出序号为 ``index``,其中
``0 <= index < levelSize``。最终写入位置为:
.. code-block:: text
从左到右:targetIndex = index
从右到左:targetIndex = levelSize - 1 - index
第二个公式把序号 ``0,1,...,levelSize-1`` 映射为逆序的
``levelSize-1,...,1,0``。它是同一组下标上的一一映射,所以每个节点值恰好写入一个槽位,每个槽位也恰好
接收一个值,不需要插入、移动或反转。
``writeToTargetPositions`` 先把 ``level`` 预分配为当前层大小,再按方向计算 ``targetIndex``。与直觉法相比,
队列、层大小快照和孩子入队逻辑全部不变;只把“尾部追加后反转”替换为“直接写入最终下标”。这正是锯齿
要求带来的最小状态变化。
状态走读
~~~~~~~~
对 ``[8,4,12,2,6,10,14,null,3]``,每层开始时的队列仍保持自然的从左到右顺序:
.. list-table::
:header-rows: 1
* - 深度
- 队列中的当前层
- ``leftToRight``
- 写入下标
- 当前行
- 下一层队列
* - 0
- ``[8]``
- ``true``
- ``[0]``
- ``[8]``
- ``[4,12]``
* - 1
- ``[4,12]``
- ``false``
- ``[1,0]``
- ``[12,4]``
- ``[2,6,10,14]``
* - 2
- ``[2,6,10,14]``
- ``true``
- ``[0,1,2,3]``
- ``[2,6,10,14]``
- ``[3]``
* - 3
- ``[3]``
- ``false``
- ``[0]``
- ``[3]``
- ``[]``
深度 ``1`` 中,``4`` 先出队却写入下标 ``1``,``12`` 后出队写入下标 ``0``;与此同时,孩子仍由 ``4``
开始按左、右方向入队,所以深度 ``2`` 的队列保持 ``[2,6,10,14]``。单节点层的正序和逆序映射都只有
下标 ``0``,不会成为特殊情况。
分支与主解选择
~~~~~~~~~~~~~~
空树在建立队列前返回 ``{}``。非空树中,``levelSize`` 必须在处理本层前保存,否则新入队的孩子会混入
当前行。左右孩子分支只决定哪些实际节点进入下一层,不加入空占位;方向分支只选择写入下标。三类状态各自
承担一个职责,互不污染。
公开入口采用 ``writeToTargetPositions``。它与反转法具有相同的线性复杂度,但每个节点值只写入最终位置
一次,不需要额外的奇数层扫描。双端队列头插也能避免反转,却要再把双端队列转换为返回所需的 ``vector``,
没有比下标映射带来新的状态认识,因此不再保留为第三种实现。
复杂度分析
~~~~~~~~~~
两种方法都让每个节点入队、出队一次,时间为 ``O(n)``;反转法对奇数层的额外扫描总量仍为 ``O(n)``。
队列最多保存一层与下一层的部分节点,工作空间为 ``O(w)``,其中 ``w`` 是最大层宽。每层向量最终属于返回
结果,全部行合计保存 ``n`` 个值,其 ``O(n)`` 空间不计入工作空间。