题目简述

        给定二叉树的根节点，打印二叉树的每一层，奇数层正序，偶数层逆序。

算法一（栈）:

时间复杂度：O(N)

思路：

        根据栈先进后出的特性，开两个栈，L 栈负责正序，R 栈负责逆序。
        1. L栈中取左右儿子时按先左后右顺序存入R栈。
        2. R栈中取左右儿子时按先右后左顺序存入L栈。
            例如：{8,6,10,5,7,9,11,12,13,14,15,16,17,18,19} 
                (1)    L={ 8 }   R={ }                                         取出  ：  8
                (2)    L={ }      R={6,10}                                   取出 ：   10，6
                (3)    L={11,9,7,5}  R={ };                                 取出 ：   5，7，9，11
                (4)    L={ }      R={12,13,14,15,16,17,18,19}   取出：    19,18,17,16,15,14,13,12

代码: 

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        stack<TreeNode*> l;
        stack<TreeNode*> r;
        vector<vector<int> > ans;
        if(pRoot) l.push(pRoot);
        while(l.size()||r.size())
        {
            int lenL=l.size(); 
            int lenR=r.size();
            vector<int> res;
            //两个for只能进去一个
            for(int i=0;i<lenL;i++){ //正序
                auto root=l.top();
                l.pop();
                res.push_back(root->val);
                if(root->left) r.push(root->left);    //先左后右
                if(root->right) r.push(root->right);
            }
            for(int i=0;i<lenR;i++){//倒序
                auto root=r.top();
                r.pop();
                res.push_back(root->val);
                if(root->right) l.push(root->right);    //先右后左
                if(root->left) l.push(root->left);
            }
            ans.push_back(res);
        }
        return ans;
    }
};

算法二（队列）:

时间复杂度：O(N)

思路:

        1、 对于每层先正常存入vector中，然后判断该层是否需要翻转。
        2、 存入操作：
                        (1)  先记录目前队列元素的个数size，这么多为树的同一层。
                        (2)  由于队列取出是从队首取，而插入是在队尾。那么我们取队首元素时，不断在队尾插入左右儿子，队列的顺序不变。
                        (3) 当我们取完前size时该层清空，队列此时为下一层的节点。
        3、 判断操作：
                        由于是正序和逆序是交错的，所以我们直接利用mark的奇偶性即可，每层操作时都对mark++即可。

图解：


代码: 

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        queue<TreeNode*> q;
            vector<vector<int> > ans;
            if(pRoot) q.push(pRoot);
            int mark=0;
            while(q.size())
            {
                mark++;
                int len=q.size();
                vector<int> res;
                for(int i=0;i<len;i++){ //将该层存入
                    auto root=q.front();
                    q.pop();
                    if(root->left) q.push(root->left);
                    if(root->right) q.push(root->right);
                    res.push_back(root->val);
                }
                if(mark%2==0) reverse(res.begin(),res.end()); //将数组翻转
                ans.push_back(res); 
            }
            return ans;
    }
    
};