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

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

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

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

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;
        if(pRoot==NULL){
            return res;
        }
        
        queue<TreeNode*> Q;
        Q.push(pRoot);
        Q.push(NULL);
        vector<int> 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<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;

        if (pRoot == NULL){
            return res;
        }
        
        queue<TreeNode*> q;
        q.push(pRoot);

        while (!q.empty()){
            int lo = 0, hi = q.size();
            vector<int> 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<vector<int> > 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;
}