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

class Solution {
public:
    //核心思路使用了一个队列一个栈。队列是层序遍历常用的，不多赘述。
    //如果不使用栈的话，我们只能做到对每个节点的子节点进行方向转换。
    //而题目的要求是要对一整层都进行方向的转换。
    vector<vector<int> > Print(TreeNode* pRoot) {
        queue<TreeNode*> BQueue;
        stack<TreeNode*> BStack;
        vector<vector<int> >result;
        vector<int>OneLayer;
        //true代表本行是从左往右，false代表从右往左。
        //本行是从左往右，将子结点入栈时自然也是先左后右，弹出时方向自然就反了。
        bool direction=true;
        if(pRoot==NULL)
            return result;
        //这层的每一个节点视为一个父节点，下一层的每一个节点视为一个子节点。
        int parents=1;
        int children=0;
        BQueue.push(pRoot);
        while(!BQueue.empty())
        {
            TreeNode* Current=NULL;
            //出队一个父结点
            Current=BQueue.front();
            OneLayer.push_back(Current->val);
            BQueue.pop();
            parents--;
            //将这个父节点的子节点入栈，方向由direction控制。
            //true为先左后右
            if(direction==true){
                if(Current->left!=NULL){
                    BStack.push(Current->left);
                    children++;
                }
                if(Current->right!=NULL){
                    BStack.push(Current->right);
                    children++;
                }
            }//false:先右后左。
            else{
                if(Current->right!=NULL){
                    BStack.push(Current->right);
                    children++;
                }
                if(Current->left!=NULL){
                    BStack.push(Current->left);
                    children++;
                }
            }
            //如果这一层的节点都出队（处理）完了，就要开始进入下一层了。
            if(parents==0)
            {
                //下一层的方向改变。
                direction=(direction==true)? false:true;
                //到了下一层后，原本的子节点变成了新的父节点。
                parents=children;
                children=0;
                //将这一层的打印结果保存起来。
                result.push_back(OneLayer);
                OneLayer.clear();
                //将栈中的内容倾倒队列，即将下一层的子节点入队。
                while(!BStack.empty())
                {
                    BQueue.push(BStack.top());
                    BStack.pop();
                }
            }
        }
        return result;
    }
    
};