题目链接

牛客网

题目描述

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

输入：
{8,6,10,5,7,9,11}
输出：
[[8],[6,10],[5,7,9,11]]

解题思路

方法：队列

层次遍历打印二叉树，用队列实现。
有一句话，我觉得说的特别好：做题=解法+模板，意思就是说，对于一道题目，首先明白正确的解法已经解决该问题70%，剩下的就直接套模板。

所以BFS的模板为：

如果不需要确定当前遍历到了哪一层，模板如下：

void bfs() {
 vis[] = {0}; // or set
 queue<int> pq(start_val);

 while (!pq.empty()) {
     int cur = pq.front(); pq.pop();
     for (遍历cur所有的相邻节点nex) {
         if (nex节点有效 && vis[nex]==0){
             vis[nex] = 1;
             pq.push(nex)
         }
     } // end for
 } // end while
}

上述是伪代码，不仅可用于二叉树，可针对所有用BFS解题。

1. 如果需要确定遍历到哪一层，模板如下：
   

   void bfs() {
   int level = 0;
   vis[] = {0}; // or set
   queue<int> pq(original_val);
   while (!pq.empty()) {
     int sz = pq.size();
   
     while (sz--) {
             int cur = pq.front(); pq.pop();
         for (遍历cur所有的相邻节点nex) {
             if (nex节点有效 && vis[nex] == 0) {
                 vis[nex] = 1;
                 pq.push(nex)
             }
         } // end for
     } // end inner while
     level++;
   
   } // end outer while
   }
   

   以此题可直接套用模板，代码如下： ```cpp / 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) {
        if(pRoot==nullptr) return {};
        vector<vector<int>> ret;
        queue<TreeNode*> pq;
        pq.push(pRoot);
        while(!pq.empty()){
            int sz = pq.size();
            vector<int> ans;
            while(sz--){
                TreeNode* node = pq.front();
                pq.pop();
                ans.push_back(node->val);
                if(node->left!=nullptr) pq.push(node->left);
                if(node->right!=nullptr) pq.push(node->right);
            }
            ret.push_back(ans);
        }
        return ret;
    }
   

}; ```

• 时间复杂度：O(N)
• 空间复杂度：O(1), vecotr> 是必须要开的，不算在额外空间里