剑指offer-把二叉树打印成多行

本文为剑指 offer 系列第五十七篇。
主要知识点为二叉树，就是简单的层序遍历而已。

题目描述

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

解题思路

就是简单的层序遍历。
用队列保存每一层的结果，方便遍历下一层，
同时本层的结果放到一个数组中进行存储。
所有层数组的集合就是我们的最终结果。

解题代码

/*
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* root) {
            if(!root) return {};
            vector<vector<int>> res;
            queue<TreeNode*> q{{root}};
            while(!q.empty()){
                vector<int> level;
                for(int i = q.size();i>0;i--){
                    auto a = q.front(); q.pop();
                    level.push_back(a->val);
                    if(a->left) q.push(a->left);
                    if(a->right) q.push(a->right);
                }
                res.push_back(level);
            }
            return res;
        }
    
};

时间复杂度为O(n),空间复杂度为O(n)

以上，本题结束！