无论是LeetCode的题目还是竞赛题，很多都有关对二叉树的操作，因此有必要对做过的题目进行一番总结。
二叉树的层次遍历
BFS方式实现（队列）
要注意队列的结点类型！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == NULL)
return {};
queue<TreeNode*> q;
q.push(root);
int cnt;
while(!q.empty()){
vector<int>level;
cnt = q.size();
while(cnt--){
TreeNode* tmp = q.front();
q.pop();
level.push_back(tmp->val);
if(tmp->left)
q.push(tmp->left);
if(tmp->right)
q.push(tmp->right);
}
res.push_back(level);
}
return res;
}
|
DFS版（递归）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<vector<int>>res;
vector<vector<int>> levelOrder(TreeNode* root) {
DFS(root,0);
return res;
}
void DFS(TreeNode* root, int level){
vector<int>ans;
if(root == NULL)
return;
if(res.size() == level)
res.resize(level+1);
res[level].push_back(root->val);
if(root->left)
DFS(root->left,level+1);
if(root->right)
DFS(root->right,level+1);
}
|
