版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 4.0
二叉树的遍历
二叉树的先序、中序、后序说的都是根相对的位置来说的。
- 先序（先根）：根-左-右
- 中序（中根）：左-根-右
- 后序（后根）：左-右-根
比如，有如下二叉树：
则我们可以知道
- 先序：preorder = [1,2,4,3,5]
- 中序：inorder = [2,4,1,3,5]
- 后序：postorder = [4,2,5,3,1]
下面介绍的是后序遍历算法，分别使用递归和非递归方法。
递归方法
算法首先遍历左子树，然后遍历右子树，最后是根节点。
1
2
3
4
5
6
7
8
9
10
11
12
|
vector<int> postorderTraversal(TreeNode *root) {
vector<int> ans;
postorder(root, ans);
return ans;
}
void (TreeNode *root, vector<int> &ans) {
if (!root) return;
postorder(root->left, ans);
postorder(root->right, ans);
ans.push_back(root->val);
}
|
非递归方法
可以用栈或 Morris 遍历
1. 栈
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
|
vector<int> Trees::postorderTraversal(TreeNode* root)
{
vector<int> ans;
stack<const TreeNode*> s;
const TreeNode *p, *q;
p = root;
do {
while (p) {
s.push(p);
p = p->left;
}
q = nullptr;
while (!s.empty()) {
p = s.top();
s.pop();
if (p->right == q) {
ans.push_back(p->val);
q = p;
}
else {
s.push(p);
p = p->right;
break;
}
}
} while (!s.empty());
return ans;
}
|
2. Morris
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
vector<int> Trees::postorderTraversal_Morris(TreeNode* root)
{
vector<int> ans;
TreeNode fake(-1);
TreeNode *cur, *prev = nullptr;
function< void(const TreeNode*) > visit = [&ans](const TreeNode *node) {
ans.push_back(node->val);
};
fake.left = root;
cur = &fake;
while (cur != nullptr)
{
if (cur->left == nullptr)
{
prev = cur;
cur = cur->right;
}
else
{
TreeNode *node = cur->left;
while (node->right != nullptr && node->right != cur)
{
node = node->right;
}
if (node->right == nullptr)
{
node->right = cur;
prev = cur;
cur = cur->left;
}
else
{
visit_reverse(cur->left, prev, visit);
prev->right = nullptr;
prev = cur;
cur = cur->right;
}
}
}
return ans;
}
void Trees::reverse(TreeNode *from, TreeNode *to)
{
TreeNode *x = from, *y = from->right, *z;
if (from == to) return;
while (x != to)
{
z = y->right;
y->right = x;
x = y;
y = z;
}
}
void Trees::visit_reverse(TreeNode *from, TreeNode *to,
function< void(const TreeNode*) >& visit)
{
TreeNode *p = to;
reverse(from, to);
while (true)
{
visit(p);
if (p == from) break;
p = p->right;
}
reverse(to, from);
}
|
较复杂，可以参考 Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）- cnblogs
END.
近期评论