二叉树宽度优先遍历和深度优先遍历(前序 中序 后序)及c++中的set map
二叉树的宽度优先遍历
如下图二叉树：
graph TB
1((1))
2((2))
3((3))
4((4))
5((5))
6((6))
7((7))
1-->2
1-->3
2-->4
2-->5
3-->6
3-->7
广度优先搜索借助队列实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| CBTInserter(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
TreeNode* node =q.front();
cout<<node->val<<endl;
q.pop();
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
}
|
剑指 Offer II 043. 往完全二叉树添加节点 - 力扣（Leetcode）
该题的思路是对完全二叉树进行层次遍历，找到没有左右子节点的叶子节点，并将这些叶子节点放入待选队列。
在insert方法中向待选队列中的叶子节点插入子节点。
二叉树的深度优先遍历
递归
- 前序遍历
1
2
3
4
5
6
7
| void dfs(TreeNode* root){
if(root!=null){
cout<<root<<endl;
dfs(root->left);
dfs(root->right);
}
}
|
- 中序遍历
1
2
3
4
5
6
7
| void dfs(TreeNode* root){
if(root!=null){
dfs(root->left);
cout<<root<<endl;
dfs(root->right);
}
}
|
- 后序遍历
1
2
3
4
5
6
7
| void dfs(TreeNode* root){
if(root!=null){
dfs(root->left);
dfs(root->right);
cout<<root<<endl;
}
}
|
迭代
- 前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void preorder(TreeNode *root){
stack<TreeNode*> s;
TreeNode* cur;
while(cur!=NULL||s.empty()!=true){
while(cur!=NULL){
cout<<cur<<endl;
s.push(cur);
cur=cur->left;
}
cur=s.top();
s.pop();
cur=cur->right;
}
}
|
- 中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void inorder(TreeNode *root){
stack<TreeNode*> s;
TreeNode* cur;
while(cur!=NULL||s.empty()!=true){
while(cur!=NULL){
s.push(cur);
cur=cur->left;
}
cout<<cur<<endl;
cur=s.top();
s.pop();
cur=cur->right;
}
}
|
- 后序遍历
后序遍历可以利用两个栈实现：
- 先将根节点入栈1
- 将根节点入栈2，并将根节点的左右子节点(先左再右)入栈1
- 以此类推，从栈1进入栈2的节点顺序是头右左，栈2出栈顺序是左右头
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void postorder(TreeNode *root){
stack<TreeNode*> s1;
stack<TreeNode*> s2;
s1.push(root);
TreeNode*cur;
while(s1.empty()!=NULL){
cur=s1.top();
s1.pop();
if(cur->left!=NULL){
s2.push(cur->left);
}
if(cur->right!=NULL){
s2.push(cur->right);
}
}
while(s2.empty!=true){
cout<<s2.top();
s2.pop();
}
}
|
set&map
set和map共同点：