[AcWing]44. 分行从上往下打印二叉树

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

数据范围

树中节点的数量 [0,1000]。

样例

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

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

算法思想1

已知不分行的做法是使用BFS层序遍历这棵树。

在此基础上，做出一些改变，即可得到不分行的做法。

问：在BFS的过程中，能否知道当前队列中有多少节点？

答：可以。队列的容量就是当前层的节点数量

那么，在第1层，只有根节点，队列容量是1，当前层节点数量是1。

在第2层，有2个节点，队列容量是2，当前层节点数量是2。

原BFS每次只能弹出一个节点，如果我们一次性弹出当前层数的节点呢？然后将它放入小集合。

这样一轮结束，将小集合放入大集合。

代码实现1

/**
 * 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>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> ans;
        // 如果是空树返回空集合
        if(!root) return ans;
        
        // BFS
        queue<TreeNode *> q;
        // 从根节点开始扩展
        q.push(root);
        
        while(q.size()){
            // 当前层的元素个数
            int len = q.size();
            
            // 用来保存当前层的值的集合
            vector<int> level;
            
            // 一次性将当前层的所有节点弹出
            while(len --){
                // 从队头开始弹出
                TreeNode * t = q.front();
                q.pop();
                // 记录这层值的元素
                level.push_back(t -> val);
                
                // 为一次性弹出下层节点做准备
                if(t -> left) q.push(t -> left);
                if(t -> right) q.push(t -> right);
            }
            // 将小集合放入大集合
            ans.push_back(level);
        }
        
        return ans;
    }
};

算法思想2

代码实现2

/**
 * 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>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> ans;
        // 空树，返回空集合
        if(!root) return ans;
        
        // 基于BFS的分行操作
        queue<TreeNode *> q;
        q.push(root); // 从根节点开始BFS
        q.push(NULL); // 代表这层结束
        
        // 存储每层的节点值
        vector<int> level;
        
        while(q.size()){
            TreeNode * t = q.front();
            q.pop();
            
            // 如果当前层结束了
            if(!t){
                // 如果下一层没有节点了
                // 比如：4 NULL，while循环拿出4，放入level之后，取出NULL，进入这个if条件里面
                // level不是空，因此提交 level 到 ans 里面
                // 队列里面剩下的是 NULL，再拿出来，此时判断level，为空，break掉
                // 这也就是下一层没有节点的情况
                if(level.empty()) break;
                // 当前层结束了，下一行还有节点，先提交level，再给下一层增加结束标识符
                ans.push_back(level);
                q.push(NULL);
                // 为了下一次，level容器是空的，还需要还原空状态
                level.clear();
                continue;
            }
            // 当前层没结束,正常BFS
            level.push_back(t -> val);
            if(t -> left) q.push(t -> left);
            if(t -> right) q.push(t -> right);
        }
        
        return ans;
    }
};