当前位置 博文首页 > 中流击水,浪遏飞舟:层序遍历&&剑指 Offer 32 - II. 从
其他博主那里看的一句话:dfs优先考虑递归,bfs优先考虑queue。
queue队列遍历,不断入队和出队。
参考:
C++ 二叉树的层次遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
cout<<q.front()->val<<" ";
if(q.front()->left){
q.push(q.front()->left);
}
if(q.front()->right){
q.push(q.front()->right);
}
q.pop();
}
参考学习大佬的力扣题解:
面试题32 - II. 从上到下打印二叉树 II(层序遍历 BFS,清晰图解)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> q;
if(root){
q.push(root); //细节:防止root空时q还push,q.front()就会报错
}
while(!q.empty()){
vector<int>tmp;
for(int i=q.size();i>0;i--){ //控制层次的细节
int t=q.front()->val;
tmp.push_back(t);
if(q.front()->left){
q.push(q.front()->left);
}
if(q.front()->right){
q.push(q.front()->right);
}
q.pop();
}
ans.push_back(tmp);
}
return ans;
}
};
cs