题解 | #牛群Z字型排列#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

二叉树遍历，队列的应用。

题目解答方法的文字分析

这个题目要求我们按照Z字形（Zigzag）的顺序遍历二叉树的每一层，并将每一层的节点值存储在一个二维向量中。我们可以使用队列来进行层次遍历，同时用一个标志位来表示当前层遍历的方向（从左到右或从右到左）。

具体步骤如下：

1. 初始化一个队列，将根节点入队。
2. 使用一个标志位 isLeftToRight 表示当前层遍历的方向，初始化为 true。
3. 在每一层的遍历开始前，获取当前队列的大小，即当前层的节点数量。
4. 循环遍历当前层的节点：如果 isLeftToRight 为 true，从队列的头部取出节点，将其值加入当前层的向量中，并将其左右子节点分别入队。如果 isLeftToRight 为 false，从队列的尾部取出节点，将其值加入当前层的向量中，并将其右子节点和左子节点分别入队。
5. 当前层遍历结束后，将当前层的向量加入结果向量中。
6. 切换 isLeftToRight 的值，进行下一层的遍历。

本题解析所用的编程语言

C++

完整且正确的编程代码

/**
 * Definition for binary tree.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
class Solution {
public:
    vector<vector<int> > ZLevelOrder(TreeNode* root) {
        vector<vector<int>> result; // 存储最终的结果
        if (!root) {
            return result; // 空树直接返回空结果
        }

        queue<TreeNode*> q; // 队列用于层次遍历
        q.push(root); // 将根节点入队
        bool isLeftToRight = true; // 标志位，初始为从左到右遍历

        while (!q.empty()) {
            int levelSize = q.size(); // 当前层的节点数
            vector<int> levelNodes(levelSize); // 存储当前层的节点值

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front(); // 取出队首节点
                q.pop();

                int index = isLeftToRight ? i : levelSize - i - 1; // 根据遍历方向确定节点在向量中的位置
                levelNodes[index] = node->val; // 将节点值存储在向量中

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

            result.push_back(levelNodes); // 将当前层的向量存储在结果中
            isLeftToRight = !isLeftToRight; // 切换遍历方向
        }

        return result; // 返回最终结果
    }
};

在这份代码中，我们首先判断根节点是否为空，如果是空树，则直接返回一个空的结果向量。接着我们使用队列进行层次遍历，同时通过 isLeftToRight 标志位来控制每层的遍历方向。在遍历每一层时，我们先获取当前层的节点数，然后创建一个向量 levelNodes 来存储当前层的节点值。在遍历当前层的每个节点时，根据 isLeftToRight 的值，确定节点在向量中的位置，然后将节点值存储在相应位置。同时，如果节点有左子节点，则将左子节点入队，如果有右子节点，则将右子节点入队。最后，将存储了当前层节点值的向量 levelNodes 加入结果向量 result 中，然后切换 isLeftToRight 的值，进行下一层的遍历。

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！