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

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <deque>
#include <vector>
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        //偶数层从右到左，奇数层从左到右  
        vector<vector<int> > arr;
        if(pRoot == nullptr) return arr;
        TreeNode* Node = pRoot;
        std::deque<TreeNode* > deq;
        int size = 1;  //该层的元素数
        int i = 1; //层数 
        deq.push_back(Node);
        while(!deq.empty())
        {
            vector<int > arrtemp;
            //处理本层元素
            while(size--)
            {
                Node = deq.front();
                deq.pop_front();
                arrtemp.push_back(Node->val);
                //下一层元素进队
                if(Node->left != nullptr) deq.push_back(Node->left);
                if(Node->right != nullptr) deq.push_back(Node->right);
            }
		  	//处理 当层数为偶数，将arrtemp反转，再存入arr中
		  	//为奇数则不需要操作，直接存arrtemp
            if(i%2 != 1)
            {
                vector<int > rarrtemp(arrtemp.rbegin(),arrtemp.rend());
                arr.push_back(rarrtemp);
            }
            else 
            {
                arr.push_back(arrtemp);
            }
            ++i;
            size = deq.size();
        }
        return arr;

    }
    
};