NC14 #二叉树的之字形层序遍历#

同样是用队列维护，但是多用了一个栈用来反转。

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        vector<vector<int> > vec;
        if(root == nullptr) return vec;
        queue<TreeNode*> que;
        int flag = 0;
        que.push(root);
        while(!que.empty())
        {
            int len = que.size();
            vector<int> tempVec;
            stack<int> stk;
            for(int i = 0; i < len; i++)
            {
                TreeNode *temp = que.front();
                if(temp->left != nullptr) que.push(temp->left);
                if(temp->right != nullptr) que.push(temp->right);
                if(flag % 2) stk.push(temp->val);
                else tempVec.push_back(temp->val);
                que.pop();
            }
            if(flag % 2)
                while(!stk.empty())
                {
                    tempVec.push_back(stk.top());
                    stk.pop();
                }
            vec.push_back(tempVec);
            flag++;
        }
        return vec;
    }
};