题目描述

给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。

例如： 给定的二叉树是{1,2,3,#,#,4,5}

该二叉树多行打印层序遍历的结果是 [ [1], [2,3], [4,5] ]

数据范围：二叉树的节点数 10000≤n≤1000， 10000≤val≤1000
要求：空间复杂度 O(n)，时间复杂度 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) {
            vector<vector<int>> v;
            if(!pRoot) return v;
            queue<TreeNode *> q;
            q.push(pRoot);
            while(!q.empty()){
                vector<int> arr;
                int size = q.size();
                for(int i =0;i<size;i++){//注意：这里的size在循环体中国不能改变，所以这里不能直接使用q.size()
                    TreeNode * temp = q.front();
                    arr.push_back(temp->val);
                    q.pop();
                    if(temp->left)
                        q.push(temp->left);
                    if(temp->right)
                        q.push(temp->right);
                }
                v.push_back(arr);
            }
            return v;
        }
};