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

考察的知识点：二叉树的层次遍历；

解答方法分析：

1. 判断根节点是否为空，为空则返回一个空的整型二维向量。
2. 创建一个队列 q，并将根节点入队。
3. 创建一个空的有序列表 level 用于保存当前层的节点值。
4. 创建一个布尔变量 leftToRight，用于标记当前层是否从左到右遍历，初始值为 true。
5. 进入循环，直到队列为空：获取当前层的节点数量 size，清空有序列表 level，循环遍历当前层的节点：出队一个节点 node，根据遍历方向 leftToRight，将节点值插入有序列表 level。如果节点有左子节点，将左子节点入队；如果节点有右子节点，将右子节点入队。将有序列表 level 加入结果二维向量 res，切换遍历方向 leftToRight。
6. 返回结果二维向量 res。

所用编程语言：C++；

完整编程代码：↓

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > ZLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }

        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;  // 用来标记当前层遍历的方向

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

            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front();
                q.pop();

                // 根据遍历的方向，将节点值放入当前层的的对应位置
                if (leftToRight) {
                    level[i] = node->val;
                } else {
                    level[size - i - 1] = node->val;
                }

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

            // 改变遍历方向
            leftToRight = !leftToRight;

            res.push_back(level);
        }

        return res;
    }
};