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

层序遍历的变体：使用队列完成层序遍历时，增加一个last指针，指向每一层的最后一个节点。设置一个flag标志，用来记录该层是从左排列还是从右排列。每层最后一个节点出队时，进行左右交换即可。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<int> temp_vec;
        vector<vector<int>> res;
        vector<TreeNode *> que;
        int front = 0, rear = 1;
        int last = 1;
        bool flag = true;
        if(!pRoot)return res;
        que.push_back(pRoot);
        while(front != rear) {
            TreeNode* cur = que[front++];
            if(flag)
                temp_vec.push_back(cur->val);
            else temp_vec.insert(temp_vec.begin(), cur->val);
            if(cur->left) {
                que.push_back(cur->left);
                rear++;
            }
            if(cur->right) {
                que.push_back(cur->right);
                rear++;
            }
            if(last == front){
                res.push_back(temp_vec);
                flag = !flag;
                last = rear;
                temp_vec.clear();
            }
        }
        return res;
    }
};