题解 | #按之字形顺序打印二叉树#

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        if(pRoot == NULL) return {};   //为空返回空
        int index = 0;   //记录是奇数层还是偶数层
        stack<int> sta;   //栈用作奇数行反向输出val
        queue<TreeNode* > deq;  //队列用作模拟层次遍历（BFS），原来用的是双端队列，改成队列了
        vector<int> temp;   //存储小的vector
        vector<vector<int> > res;   //存结果
        TreeNode* p = pRoot;
        deq.push(p);  //根节点入双端队列
        while(deq.size() != 0){   //队列为空说明遍历完成
            if(index % 2 == 0){     //偶数层正常执行层次遍历
                int x = deq.size();
                while(x--){
                    temp.push_back(deq.front()->val);
                    if(deq.front()->left != NULL) deq.push(deq.front()->left);
                    if(deq.front()->right != NULL) deq.push(deq.front()->right);
                    deq.pop();
                }
                index++;
                res.push_back(temp);
                temp.clear();
                continue;
            }
            if(index % 2 == 1){    //奇数层进栈实现反向输出
                int x = deq.size();
                while(x--){
                    if(deq.front()->left != NULL) deq.push(deq.front()->left);
                    if(deq.front()->right != NULL) deq.push(deq.front()->right);
                    sta.push(deq.front()->val);
                    deq.pop();
                }
                while(sta.size() != 0){
                    temp.push_back(sta.top());
                    sta.pop();
                }
                index++;
                res.push_back(temp);
                temp.clear();
                continue;
            }
        }
        return res;
    }
    
};