04、二叉树的锯齿形层序遍历

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

题目描述

给你二叉树的根节点root，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

        3
       / \
      9  20
        /  \
       15   7

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

数据范围：

• 树中节点数目在范围 [0, 2000] 内
• -100 <= Node.val <= 100

题目分析

这道题是层序遍历的变体，该题目的关键就是关键在于锯齿形，如下

• 第 1 层（根节点）：从左到右
• 第 2 层：从右到左
• 第 3 层：从左到右
• 第 4 层：从右到左
• ...以此类推

也就是我们所理解的 Z 字型遍历，那其实到这里就好理解了

核心思路

1. 基于标准的 BFS 层序遍历
2. 使用一个标志位控制当前层的遍历方向
3. 奇数层从左到右，偶数层从右到左（或相反，取决于如何定义）

那这样我们通过标志位，和层序遍历就可以解决这个题目啦，下面是这道题的注意事项

• 需要区分每一层
• 需要根据层数决定添加节点的顺序
• 可以通过反转或使用双端队列实现

BFS + 反转（推荐）

1. 标准的 BFS 层序遍历
2. 使用布尔变量 leftToRight 控制方向
3. 每层遍历完后，根据方向决定是否反转当前层结果（借助标志位）

图解过程

以 root = [3,9,20,null,null,15,7] 为例：

初始状态：
        3
       / \
      9  20
        /  \
       15   7

第 1 层（从左到右）：
队列：[3]
当前层：[3]
结果：[[3]]

第 2 层（从右到左）：
队列：[9, 20]
当前层：[9, 20] → 反转 → [20, 9]
结果：[[3], [20, 9]]

第 3 层（从左到右）：
队列：[15, 7]
当前层：[15, 7]
结果：[[3], [20, 9], [15, 7]]

C++ 实现

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;

        // 特殊情况：空树
        if (root == nullptr) {
            return result;
        }

        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;  // 控制遍历方向

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;

            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);

                // 将子节点加入队列
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }

            // 根据方向决定是否反转当前层
            if (!leftToRight) {
                reverse(currentLevel.begin(), currentLevel.end());
            }

            result.push_back(currentLevel);
            leftToRight = !leftToRight;  // 切换方向
        }

        return result;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次，反转操作总共是 O(n)。

空间复杂度：O(n)。队列中最多存储一层的节点。

这个题目也可以借助双端队列来完成，大家可以试一下