二叉树的遍历方法总结
|
二叉树的遍历方法总结
二叉树的遍历有前序遍历，中序遍历，后续遍历和层序遍历，这几种方法都可以通过递归和循环来实现。
二叉树数据结构定义
1 | /** |
二叉树的前序遍历
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if(!root){
return {};
}
vector<int> res;
preorderTraversal(root,res);
return res;
}
void preorderTraversal(TreeNode* root, vector<int>& res){
if(!root){
return;
}
res.push_back(root->val);
preorderTraversal(root->left,res);
preorderTraversal(root->right,res);
return;
}
};循环实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if(!root){
return {};
}
vector<int> res;
stack<TreeNode*> nodes;
nodes.push(root);
while(!nodes.empty()){
TreeNode* node = nodes.top();
nodes.pop();
res.push_back(node->val);
if(node->right){
nodes.push(node->right);
}
if(node->left){
nodes.push(node->left);
}
}
return res;
}
};
二叉树的中序遍历
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return{};
vector<int> res;
inorderTraversal(root,res);
return res;
}
void inorderTraversal(TreeNode* root, vector<int>& res){
if(!root){
return;
}
inorderTraversal(root->left, res);
res.push_back(root->val);
inorderTraversal(root->right,res);
}
};循环实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> res;
TreeNode* r = root;
while(!s.empty() || r!=NULL){
while(r!=NULL){
s.push(r);
r = r->left;
}
r = s.top();
s.pop();
res.push_back(r->val);
r=r->right;
}
return res;
}
};
二叉树的后序遍历
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return {};
postorderTraversal(root,res);
return res;
}
void postorderTraversal(TreeNode* root, vector<int>& res){
if(!root){
return;
}
postorderTraversal(root->left,res);
postorderTraversal(root->right,res);
res.push_back(root->val);
}
};循环实现
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
28class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
if(!root) return {};
stack<TreeNode*> nodes;
vector<int> res;
TreeNode* pre = NULL;
nodes.push(root);
while(!nodes.empty()){
TreeNode* node = nodes.top();
if( (node->left==NULL && node->right==NULL) ||
(pre!=NULL && (node->left==pre || node->right==pre))){
pre = node;
res.push_back(node->val);
nodes.pop();
}else{
if(node->right){
nodes.push(node->right);
}
if(node->left){
nodes.push(node->left);
}
}
}
return res;
}
};
二叉树的层序遍历
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int> > res;
if(root==NULL) return res;
levelOrder(root,res,0);
return res;
}
void levelOrder(TreeNode* root, vector<vector<int> >&res, int level){
if(root==NULL) return;
if(res.size()==level){
res.push_back(vector<int>(1,root->val));
}else{
res[level].push_back(root->val);
}
levelOrder(root->left,res,level+1);
levelOrder(root->right,res,level+1);
return;
}
};循环实现
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
29class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int> > res;
if(!root) return res;
queue<TreeNode*> nodes;
nodes.push(root);
int level=0;
while(!nodes.empty()){
int level_size = nodes.size();
int count = 0;
res.push_back(vector<int>(0));
while(count<level_size){
TreeNode* node = nodes.front();
nodes.pop();
res[level].push_back(node->val);
count++;
if(node->left){
nodes.push(node->left);
}
if(node->right){
nodes.push(node->right);
}
}
level++;
}
return res;
}
};