算法1

(BFS) $O(n)$

在上一道题 《分行从上往下打印二叉树》熊助教版本 的基础上修改代码。
新增加了flag变量标识是否反转树的某一层。
每一层结束的时候，如果flag==true那么就用reverse()反转当前层，同时往queue里塞一个NULL做标记，以及将flag取反。

在queue里读取一个数出来之后，先看看是不是level标识符NULL(因为是BFS，当前level读完，下一个level有哪些要读的也都放在queue里了，可以在queue结尾给加一个新的NULL), 是的话再看看是不是整个树读完了(即queue里没有点了)。

时间复杂度

每个点遍历了一次，$O(n)$

C++ 代码

class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        q.push(NULL);
        vector<int> cur;
        bool flag = false;
        while (q.size()){
            auto t = q.front();
            q.pop();
            if (t){
                cur.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            } else {
                if(q.size()) q.push(NULL);
                if (flag) reverse(cur.begin(), cur.end());
                flag = !flag;
                res.push_back(cur);
                cur.clear();
            }
        }
        return res;
    }
};