BFS (Breadth-First Search)
BFS(宽度优先搜索)是按"层"的概念进行的搜索算法，利用Queue记录需要被展开的TreeNode
适合解决与层数相关的Tree题目。
BFS General Steps:
- Initialize Queue with all entry points (tree only one,graph has more than one)
- While queue is not empty a. for each node in queue (currently) b. poll out element (add to result) c. expand it , offer children to the queue in order d. increase level
实践应用
例题 102. 二叉树的层序遍历
以下为解题代码：
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root==nullptr){
return res;
}
queue<TreeNode*> queue;
queue.push(root);
while(!queue.empty()){
int size=queue.size();
vector<int> vec;
for(int i=0;i<size;i++){
TreeNode* cur=queue.front();
vec.push_back(cur->val);
if(cur->left!=nullptr){
queue.push(cur->left);
}
if(cur->right!=nullptr){
queue.push(cur->right);
}
queue.pop();
}
res.push_back(vec);
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
例题 104. 二叉树的最大深度
以下为解题代码：
1