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

考察知识点： 广度优先搜索、树的层序遍历、STL

题目分析：

 树的层序遍历一般使用一个队列，先将头节点放入队列中，然后对队列中的每个元素，首先访问这个元素，然后将该元素的左右孩子结点放入队列中，直至队列中为空。

 这道题在树的层序遍历的基础之上提出进行Z字形遍历的要求。我们使用一个bool控制加入到vector中的顺序。由于层序遍历的顺序本身是确定的，但是由于该层中的元素数量是已知的，我们可以提前确定vector的大小，在需要时将结点值从尾向前加入到vector中。

所用编程语言： 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) {
        // write code here
        if (!root) return {};
        queue<TreeNode*> cows;
        vector<vector<int>> res;
        cows.push(root);
        bool toRight = true;
        while (!cows.empty()) {
            int size = cows.size();
            vector<int> v(size);
            for (int i = 0; i < size; i++) {
                TreeNode *p = cows.front();
                cows.pop();
                if (toRight) v[i] = p->val;
                else v[size - i - 1] = p->val; 
                if (p->left) cows.push(p->left);
                if (p->right) cows.push(p->right);
            }
            toRight = !toRight;
            res.push_back(v);
        }
        return res;
    }
};