题目简述

        从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

算法一:BFS

时间复杂度：O(N)

思路：

        在遍历每层的时候记录下该点的层数，每层在队列中的顺序都是有序的。
        即：如果将一个三层的满二叉树，从跟节点依次放入队列中，那么层数顺序是按1，2，2，3，3，3，3排列。
               那么我们将在同一层的放在一个数组里即可。

代码: 

/*
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<vector<int> > res;
            if(!pRoot) return res;
            queue<pair<TreeNode*,int> > q;
            q.push({pRoot,0});
            int k=0;
            vector<int> p;
            while(q.size()){
                auto t=q.front();
                q.pop();
                auto t1=t.first;
                int pos=t.second;
                if(t1->left) q.push({t1->left,pos+1}); //先左后右遍历树的节点，保证了顺序打印
                if(t1->right) q.push({t1->right,pos+1});
                if(k==pos){
                    p.push_back(t1->val); 
                }
                else{
                    k=pos; //层树标记
                    res.push_back(p); //将上一层的值放入res中
                    p.clear();//清除上一层数组的值
                    p.push_back(t1->val); //将第k层的第一个点放进去
                }
            }
            res.push_back(p);//最后一层放入res中
            return res;
        }
    
};


算法二:

时间复杂度：O(N)

思路:

        从根节点开始，不断往从左往右下遍历，并在遍历的时候将下一个节点放入队列中。
        这样可以保证，队列中的节点都是按照每层从左往右顺序排列。
        那么我们如果从根节点可以推出第二层的大小，从第二层可以推出第三层的值，......

图解：

        

代码: 

/*
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) {
            queue<TreeNode*> q;
            vector<vector<int> > ans;
            if(pRoot) q.push(pRoot);//如果是空则直接返回
            while(q.size())
            {
                int len=q.size();//每一层的数量
                vector<int> res;
                for(int i=0;i<len;i++){//保证了每层都被清空
                    auto root=q.front();
                    q.pop();
                    if(root->left) q.push(root->left);//先左后右放入队列中保证了，顺序性。
                    if(root->right) q.push(root->right);
                    res.push_back(root->val);
                }
                ans.push_back(res);
            }
            return ans;
        }
};