给你二叉树的根节点 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
步骤1：问题定义与分析
这是一道二叉树的层序遍历变体问题，具有以下特点：
- 输入：二叉树的根节点
- 输出：二维数组，表示锯齿形层序遍历结果
- 特殊要求：相邻层的遍历方向相反（先从左到右，再从右到左，如此交替）
- 限制条件：
- 节点数范围：[0, 2000]
- 节点值范围：[-100, 100]
- 边界情况：
- 空树
- 只有一个节点的树
- 完全二叉树
- 非对称的二叉树
步骤2：算法设计与分析
最优解决方案：使用广度优先搜索（BFS）配合层次标记
- 使用队列进行层序遍历
- 用一个布尔变量记录当前层的遍历方向
- 每一层的节点值存入临时数组，根据方向决定是否翻转
时间复杂度分析：
- BFS遍历所有节点：O(n)
- 某些层需要翻转：最坏情况O(n)
- 总体时间复杂度：O(n)
空间复杂度：O(n)，队列存储节点
步骤3：代码实现
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> result; // 存储最终结果if (!root) return result; // 处理空树情况queue<TreeNode*> q; // 用于BFS的队列q.push(root);bool leftToRight = true; // 控制遍历方向的标志while (!q.empty()) {int levelSize = q.size(); // 当前层的节点数vector<int> currentLevel(levelSize); // 存储当前层的节点值// 处理当前层的所有节点for (int i = 0; i < levelSize; i++) {TreeNode* node = q.front();q.pop();// 根据方向决定节点值在当前层数组中的位置int index = leftToRight ? i : (levelSize - 1 - i);currentLevel[index] = node->val;// 将下一层的节点加入队列if (node->left) q.push(node->left);if (node->right) q.push(node->right);}result.push_back(currentLevel); // 将当前层添加到结果中leftToRight = !leftToRight; // 切换方向}return result;}
};步骤4：解题启发
这道题目给我们的启发：
- 在处理树结构时，层序遍历是一个强大的工具
- 使用标志位可以优雅地处理交替模式
- 通过控制插入位置，可以避免额外的数组翻转操作
- 边界条件的处理对于保证代码健壮性很重要
步骤5：实际应用
这种锯齿形遍历算法在实际中有很多应用场景：
-
文件系统可视化：
- 在文件浏览器中展示目录结构时，可以使用这种交错展示方式来节省水平空间
- 例如：Windows资源管理器的树状视图可以采用这种方式来优化显示效果
-
网络拓扑展示：
- 在网络监控系统中展示网络设备的层级关系
- 交错展示可以减少视觉混乱，使网络结构更清晰
具体应用示例： 假设我们正在开发一个组织架构图展示系统：
class OrgChart {struct Employee {string name;vector<Employee*> subordinates;};void displayOrgChart(Employee* ceo) {// 使用相同的锯齿形遍历算法queue<Employee*> q;q.push(ceo);bool leftToRight = true;while (!q.empty()) {int levelSize = q.size();vector<string> currentLevel;for (int i = 0; i < levelSize; i++) {Employee* emp = q.front();q.pop();currentLevel.push_back(emp->name);for (Employee* sub : emp->subordinates) {q.push(sub);}}// 根据方向决定是否翻转显示顺序if (!leftToRight) {reverse(currentLevel.begin(), currentLevel.end());}// 显示当前层级的员工displayLevel(currentLevel);leftToRight = !leftToRight;}}
};这种展示方式可以：
- 减少视觉混乱
- 优化空间使用
- 提高可读性
- 使组织结构更容易理解