《剑指offer》-逐层打印二叉树-白红宇

题目描述

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

乍一看就是一个BFS，但是因为太久没刷题都忘记了要使用queue来作为空间存储容器了。

先参考milolip的代码，写出这样的solution：

class Solution {public:    vector
    
     
       > Print(TreeNode* pRoot) {        vector
      
       
         > res;        if(pRoot==NULL){            return res;        }                queue
        
          Q;        Q.push(pRoot);        Q.push(NULL);        vector
         
           v; v.push_back(pRoot->val); res.push_back(v); v.clear(); while (!Q.empty()){ TreeNode* node = Q.front(); Q.pop(); if (node != NULL){ //v.push_back(node->val); //cout << node->val << ends; if (node->left){ Q.push(node->left); v.push_back(node->left->val); } if (node->right){ Q.push(node->right); v.push_back(node->right->val); } } else if (!Q.empty()){ //cout << "test " << endl; Q.push(NULL); res.push_back(v); v.clear(); //cout << endl; } } return res; }};

上面的代码并不太简洁的样子。

另一种写法是从评论区copy来的，又简洁，又非常直观清晰。两层while的嵌套，正好对应到数的层次遍历以及层内逐点遍历。而这种双层嵌套的循环其实并没有增加复杂度，和原来的复杂度是一样的。

class Solution_11 {public:    vector
    
     
       > Print(TreeNode* pRoot) {        vector
      
       
         > res;        if (pRoot == NULL){            return res;        }                queue
        
          q;        q.push(pRoot);        while (!q.empty()){            int lo = 0, hi = q.size();            vector
         
           v; while (lo++ < hi){ TreeNode *t = q.front(); q.pop(); v.push_back(t->val); if (t->left){ q.push(t->left); } if (t->right){ q.push(t->right); } } res.push_back(v); } return res; }};

测试代码；

void main_solution_11(){    Solution_11 s = Solution_11();    TreeNode* a = new TreeNode(8);    TreeNode* b1 = new TreeNode(6);    TreeNode* b2 = new TreeNode(10);    TreeNode* c1 = new TreeNode(5);    TreeNode* c2 = new TreeNode(7);    TreeNode* c3 = new TreeNode(9);    TreeNode* c4 = new TreeNode(1);    a->left = b1;    a->right = b2;    b1->left = c1;    b1->right = c2;    b2->left = c3;    b2->right = c4;    vector
    
     
       > q = s.Print(a);    for (int i = 0; i < q.size(); i++){        for (int j = 0; j < q[i].size(); j++){            if (j > 0){                cout << " ";            }            cout << q[i][j];        }        cout << endl;    }}int main(){    main_solution_11();    return 0;}