题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
乍一看就是一个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;
}