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

1.使用队列，遵从之前层次遍历的方法，当在偶数层时，翻转结果数组即可

• step 1：首先判断二叉树是否为空，空树没有打印结果。
• step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面
• step 3：每次进入一层，统计队列中元素的个数。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
• step 4：每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
• step 5：访问完这一层的元素后，根据层数决定将这个一维数组直接加入二维数组中还是反转后再加入，然后再访问下一层。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> reserve(vector<int> &num)
    {
        vector<int> result;
        for(int i = num.size()-1;i>=0;--i)
        {
            result.push_back(num[i]);
        }
        return result;
    }
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if(!pRoot)
            return res;
        queue<TreeNode*> q;
        q.push(pRoot);
        int layers = 1;
        TreeNode *cur;
        while(!q.empty() )
        {
            vector<int> row;
            int n = q.size();
            for(int i = 0;i<n;++i)
            {
                cur = q.front();
                q.pop();
                row.push_back(cur->val);
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
            }
            if(layers % 2 == 0)
               row = reserve(row);
            layers++;
            res.push_back(row);
        }
        return res;
    }
};

2.使用双栈（利用栈后进先出的特性）

1. 定义两个栈stk1，stk2；将根结点入栈stk1；
2. 对于下一层，应是「从右至左」打印，因此需要遍历栈stk1、访问每一个元素，并将每一元素的孩子按照「先右孩子、后左孩子」的顺序入栈stk2；将访问的结点保存；
3. 对于下一层，应是「从左至右」打印，因此需要遍历栈stk2、访问每一个元素，并将每一元素的孩子按照「先左孩子、后右孩子」的顺序入栈stk1；将访问的结点保存；
4. 重复上述操作，直至两个栈全为空。

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if(!pRoot)
            return res;
        stack<TreeNode*> s1,s2;
        s1.push(pRoot);
        int layers = 1;
        TreeNode *cur;
        while(!s1.empty() || !s2.empty())
        {
            vector<int> row;
            //单数层
            while(!s1.empty())
            {
                //从左至右打印，下一层先左孩子，后右孩子 
                cur = s1.top();
                s1.pop();
                row.push_back(cur->val);
                if(cur->left)
                    s2.push(cur->left);
                if(cur->right)
                    s2.push(cur->right);
            }
            if(!row.empty())
                res.push_back(row);
            row.clear();
            //双数层
            while(!s2.empty())
            {
                //从右至左打印，下一层先右孩子，后左孩子 
                cur = s2.top();
                s2.pop();
                row.push_back(cur->val);
                if(cur->right)
                    s1.push(cur->right);
                if(cur->left)
                    s1.push(cur->left);
            }
            if(!row.empty())
                res.push_back(row);
        }
        return res;
    } 
};