题解 | #牛群Z字型排列# 层序遍历

知识点

层序遍历 二叉树

思路

和上一道题非常类似。

要求Z字形遍历，只需要在正常的层序遍历结果后翻转奇数层的结果。或者在加入答案的时候从后向前加入即可。

时间复杂度

层序遍历，遍历每个节点1次，

AC code（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<>>
     */
    using pti = pair<TreeNode*, int>;
    vector<vector<int> > ZLevelOrder(TreeNode* root) {
        // 层序遍历
        vector<vector<int>> res;
        queue<pti> q;
        if (root) q.emplace(root, 0);
        while (q.size()) {
            auto [p, idx] = q.front();
            q.pop();
            while (res.size() <= idx) res.push_back({}); // 每次最多执行一次
            res[idx].push_back(p->val);
            if (p->left) q.emplace(p->left, idx + 1);
            if (p->right) q.emplace(p->right, idx + 1);
        }
        for (int i = 1; i < (int)res.size(); i += 2) {
            reverse(res[i].begin(), res[i].end());
        }
        return res;
    }
};