题目描述

从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。

样例

输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4

输出：[[8], [12, 2], [6], [4]]

算法

(加标记的BFS)

1. 这道题的难点在于每一行元素数量的不定。对于元素数量的不定这种题，用vector来存储再好不过。
2. 这道题解法的特点是每当遍历到一个NULL的时候，就往队列中新加一个NULL，因为NULL的出现意味着一行元素的结束。因为是BFS，所以每次遍历到第n行元素的时候，都会把n+1行的元素加进队列。
3. 所以我们在新加NULL的时候，就是往已经存储进queue，但还未遍历的那一行元素后面加NULL。
4. 整个代码的逻辑就是如果队头是元素，就把元素加进队列，然后把他的左右儿子也加进去。如果是NULL，且队列中还有元素，就说明还有下一行，就加NULL。接下来就把当前行cur加入res中，然后cur清空。
5. res是二维，cut是一维，直接加就可以。

时间复杂度

$O(n)$
因为每个节点只会被遍历一次，所以时度是$O(n)$

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > res;
    vector<int> cur;
    vector<vector<int>> bfs(TreeNode* root)
    {
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);

        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(nullptr);
                res.push_back(cur);
                cur.clear();
            }
        }

        return res;
    }
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        if(!root) return res;
        return bfs(root);
    }
};