题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路1：利用二叉树层序遍历的思想。
具体实现： 先设置一个二维数组vec，用来存放每一层的结点值，即val。
若该二叉树是个空树，就返回一个vec。
若不是空树，再设置一个队列用来存放结点。一开始将根结点入队。
当队列非空的时候，需要在循环内部遍历。另外设置两个变量分别为队首lo和队尾hi。再设置一个一维数组c，用来存放每层的结点。
每遍历一个结点的时候，队首需要+1，所以在循环内部再设置一个循环。
设置一个结点变量*t等于队列中的队首结点，将该结点值加入到一维数组中，并将结点出队。
若该结点有左孩子，将左孩子加入队列；若该节点有右孩子，将右孩子加入队列。
当从队首遍历到队尾，退出循环。将一维数组中保存的结点值，加入到二维数组中。
/*
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>> vec;
if(pRoot==NULL) return vec;
queue<TreeNode *> q;
q.push(pRoot);
while(!q.empty()) {
int lo=0,hi=q.size();
vector<int> c;
while(lo++ < hi) {
TreeNode *t=q.front();
q.pop();
c.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
vec.push_back(c);
}
return vec;
}
};
思路二：思路基本和思路一一样，但是少了变量、
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > ret;
queue<TreeNode*> que;
if(pRoot) que.push(pRoot);
while(!que.empty()){
vector<int> tmp;
int n = que.size();
while(n--){
TreeNode* node = que.front();
tmp.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
que.pop();
}
ret.push_back(tmp);
}
return ret;
}
};
思路三：两个队列交错打印
/*
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>> vec;
if(pRoot==NULL) return vec;
queue<TreeNode *> q1;
queue<TreeNode *> q2;
q1.push(pRoot);
while(!q1.empty() || !q2.empty()) {
vector<int> v1;
vector<int> v2;
while(!q1.empty()) {
v1.push_back(q1.front()->val);
if(q1.front()->left!=NULL) q2.push(q1.front()->left);
if(q1.front()->right!=NULL) q2.push(q1.front()->right);
q1.pop();
}
if(v1.size()!=0)
vec.push_back(v1);
while(!q2.empty()) {
v2.push_back(q2.front()->val);
if(q2.front()->left!=NULL) q1.push(q2.front()->left);
if(q2.front()->right!=NULL) q1.push(q2.front()->right);
q2.pop();
}
if(v2.size()!=0)
vec.push_back(v2);
}
return vec;
}
};