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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > ZLevelOrder(TreeNode* root) {
        // write code here
        // 广度优先搜索
        vector<vector<int> > ans;
        if(!root)
            return ans;

        // true表示从左向右进入队列，false表示从右到左进入队列
        bool flag = true;

        deque<TreeNode *> d;
        d.emplace_back(root);

        while(!d.empty())
        {
            int len = d.size();
            vector<int> v;
            for(int i=0; i<len; ++i)
            {
                TreeNode* t = d.front();
                d.pop_front();
                v.emplace_back(t->val);

                if(t->left)
                    d.emplace_back(t->left);
                if(t->right)
                    d.emplace_back(t->right);
            }

            if(flag)
            {
                ans.emplace_back(v);
                flag = false;
            }
            else
            {
                reverse(v.begin(), v.end());
                ans.emplace_back(v);
                flag = true;
            }
        }

        return ans;
    }
};