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

方法：辅助队列

本质依然是广度优先搜索（BFS），与层序遍历本质相同，只是在偶数层时需要进行翻转。

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;
        if (pRoot == nullptr)
            return res;

        queue<TreeNode*> q;
        q.push(pRoot);
        int num = 0;
        while (!q.empty()) {
            vector<int> temp;
            int length = q.size();
            num++;
            for (int i = 0; i < length; i++) {
                temp.push_back(q.front()->val);
                if (q.front()->left)
                    q.push(q.front()->left);
                if (q.front()->right)
                    q.push(q.front()->right);
                q.pop();
            }
            //偶数层翻转数组
            if (num % 2 == 0)
                reverse(temp.begin(), temp.end());
            res.push_back(temp);
        }
        return res;
    }
};