来自leetcode原题
二叉树前序遍历、中序遍历、后续遍历
声明：
参考慕课的liuyubobobo老师的思路！！！老师太厉害了～
有别于教科书的经典非递归实现方式，本文采用模拟系统栈的方式实现非递归，目的是有助于理解递归与栈的紧密关系。并且，三种遍历的代码形式类似，而经典非递归在后序遍历部分较之前两者有很大差异且不易理解。
前序遍历
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
34
35
36
37
38
39
40
41
42
| struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
struct Commend{
string s;
TreeNode* node;
Commend(string s, TreeNode* node): s(s), node(node){}
};
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> record;
if(!root)
return record;
stack<Commend> stack_Tree;
stack_Tree.push(Commend("run", root));
while(!stack_Tree.empty()){
Commend commend = stack_Tree.top();
stack_Tree.pop();
if(commend.s == "print"){
record.push_back(commend.node->val);
}
else{
assert(commend.s == "run");
if(commend.node->right)
stack_Tree.push(Commend("run", commend.node->right));
if(commend.node->left)
stack_Tree.push(Commend("run", commend.node->left));
stack_Tree.push(Commend("print", commend.node));
}
}
return record;
}
};
|
中序遍历
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
34
35
36
37
38
39
40
41
42
43
44
| struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
struct Commend{
string s;
TreeNode* node;
Commend(string s, TreeNode* node) : s(s), node(node) {}
};
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> record;
if(!root){
return record;
}
stack<Commend> stack_Tree;
stack_Tree.push(Commend("run", root));
while(!stack_Tree.empty()){
Commend commend = stack_Tree.top();
stack_Tree.pop();
if(commend.s == "print"){
record.push_back(commend.node->val);
}
else{
assert(commend.s == "run");
if(commend.node->right)
stack_Tree.push(Commend("run", commend.node->right));
stack_Tree.push(Commend("print", commend.node));
if(commend.node->left)
stack_Tree.push(Commend("run", commend.node->left));
}
}
return record;
}
};
|
后序遍历
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
34
35
36
37
38
39
40
41
42
43
44
45
|
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
struct Commend{
string s;
TreeNode* node;
Commend(string s, TreeNode* node) : s(s), node(node) {}
};
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> record;
if(!root){
return record;
}
stack<Commend> stack_Tree;
stack_Tree.push(Commend("run", root));
while(!stack_Tree.empty()){
Commend commend = stack_Tree.top();
stack_Tree.pop();
if(commend.s == "print"){
record.push_back(commend.node->val);
}
else{
assert(commend.s == "run");
stack_Tree.push(Commend("print", commend.node));
if(commend.node->right)
stack_Tree.push(Commend("run", commend.node->right));
if(commend.node->left)
stack_Tree.push(Commend("run", commend.node->left));
}
}
return record;
}
};
|
参考链接
https://coding.imooc.com/class/82.html
