树的遍历
3 / \ 1 5 \ / 2 4
先序: 3 1 2 5 4
中序: 1 2 3 4 5
后序: 2 1 4 5 3
层序: 3 1 5 2 4
递归
1class Recursion {
2 // 先序遍历
3 void preorder(Node *root)
4 {
5 if (!root) return;
6 cout << root->val << " ";
7 preorder(root->left);
8 preorder(root->right);
9 }
10 // 中序遍历
11 void inorder(Node *root)
12 {
13 if (!root) return;
14 inorder(root->left);
15 cout << root->val << " ";
16 inorder(root->right);
17 }
18 // 后序遍历
19 void postorder(Node *root)
20 {
21 if (!root) return;
22 postorder(root->left);
23 postorder(root->right);
24 cout << root->val << " ";
25 }
26};
迭代
1class Iteration {
2 // 先序遍历 栈
3 void preorder(Node *root)
4 {
5 stack<Node *> s;
6 s.push(root);
7
8 while (!s.empty()) {
9 Node *node = s.top();
10 s.pop();
11 cout << node->val << " ";
12 if (node->right) s.push(node->right);
13 if (node->left) s.push(node->left);
14 }
15 }
16 // 中序遍历 栈
17 void inorder(Node *root)
18 {
19 stack<Node *> s;
20 Node *cur = root;
21
22 while (cur || !s.empty()) {
23 while (cur) {
24 s.push(cur);
25 cur = cur->left;
26 }
27 cur = s.top();
28 s.pop();
29 cout << cur->val << " ";
30 cur = cur->right;
31 }
32 }
33 // 后序遍历 双栈
34 void postorder1(Node *root)
35 {
36 stack<Node *> s1, s2;
37 s1.push(root);
38
39 while (!s1.empty()) {
40 Node *cur = s1.top();
41 s1.pop();
42 s2.push(cur);
43 if (cur->left) s1.push(cur->left);
44 if (cur->right) s1.push(cur->right);
45 }
46
47 while (!s2.empty()) {
48 Node *cur = s2.top();
49 s2.pop();
50 cout << cur->val << " ";
51 }
52 }
53 // 后序遍历 栈
54 void postorder2(Node *root)
55 {
56 stack<Node *> s;
57 Node *cur = root;
58 Node *vis = nullptr;
59
60 while (cur || !s.empty()) {
61 if (cur) {
62 s.push(cur);
63 cur = cur->left;
64 continue;
65 }
66 Node *top = s.top();
67 // 右子树未访问 转到右子树
68 // 所以出栈时 右子树后一个就是双亲节点
69 if (top->right && top->right != vis) {
70 cur = top->right;
71 continue;
72 }
73 // 没有右子树 或者右子树已访问
74 s.pop();
75 vis = top;
76 cout << top->val << " "; // top
77 }
78 }
79 // 层序遍历 队列
80 void levelorder(Node *root)
81 {
82 if (!root) return;
83 queue<Node *> q;
84 q.push(root);
85 while (!q.empty()) {
86 Node *node = q.front();
87 q.pop();
88 cout << node->val << " ";
89 if (node->left) q.push(node->left);
90 if (node->right) q.push(node->right);
91 }
92 }
93};
Morris
借助队列可以实现层序遍历。借助栈可以实现先序、中序、后序遍历。
Morris遍历，借助叶子结点的空指针，不使用额外空间。用到了“线索二叉树”的概念。利用叶子结点的右空指针来存储某种遍历的后继结点。
实质是构建一个在左子树遍历完之后能返回对应父节点的线索
1class Morris {
2 // 莫里斯 先序遍历 空间复杂度O(1) 时间复杂度o(2N) = O(N)
3 void preorder(Node *root)
4 {
5 Node *cur = root;
6 while (cur) {
7 if (!cur->left) {
8 cout << cur->val << " ";
9 cur = cur->right; // 通过之前建立的线索 回到祖先
10 continue;
11 }
12 Node *pre = cur->left;
13 while (pre->right && pre->right != cur) {
14 pre = pre->right;
15 }
16 if (!pre->right) {
17 cout << cur->val << " ";
18 pre->right = cur; // 建立线索
19 cur = cur->left;
20 }
21 else {
22 pre->right = nullptr; // 删除线索
23 cur = cur->right; // 访问右子树
24 }
25 }
26 }
27
28 // 莫里斯 中序遍历 空间复杂度O(1) 时间复杂度o(2N) = O(N)
29 void inorder(Node *root)
30 {
31 Node *cur = root;
32 while (cur) {
33 if (!cur->left) {
34 cout << cur->val << " ";
35 cur = cur->right; // 通过之前建立的线索 回到祖先
36 continue;
37 }
38 Node *pre = cur->left;
39 while (pre->right && pre->right != cur) {
40 pre = pre->right;
41 }
42 if (!pre->right) {
43 pre->right = cur; // 建立线索
44 cur = cur->left;
45 }
46 else {
47 cout << cur->val << " ";
48 pre->right = nullptr; // 删除线索
49 cur = cur->right; // 访问右子树
50 }
51 }
52 }
53
54 // 莫里斯 后序遍历 空间复杂度O(1) 时间复杂度o(2N) = O(N)
55 void postorder(Node *root)
56 {
57 // 反转右子节点链
58 auto reverse = [](Node *from, Node *to) {
59 Node *x = from, *y = from->right, *z;
60 while (x != to) {
61 z = y->right;
62 y->right = x;
63 x = y;
64 y = z;
65 }
66 };
67 // 逆序输出
68 auto print = [&](Node *from, Node *to) {
69 reverse(from, to);
70 Node *p = to;
71 while (true) {
72 cout << p->val << " ";
73 if (p == from) break;
74 p = p->right;
75 }
76 reverse(to, from);
77 };
78
79 Node dummy(0, root, nullptr);
80 Node *cur = &dummy;
81 while (cur) {
82 if (!cur->left) {
83 cur = cur->right;
84 continue;
85 }
86 Node *pre = cur->left;
87 while (pre->right && pre->right != cur) {
88 pre = pre->right;
89 }
90 if (!pre->right) {
91 pre->right = cur;
92 cur = cur->left;
93 }
94 else {
95 print(cur->left, pre);
96 pre->right = nullptr;
97 cur = cur->right;
98 }
99 }
100 }
101};
树的重建
通过先序和中序遍历重建二叉树。本质是通过中序遍历找到根节点，然后在先序遍历中找到对应的子树。
中序: 9 3 15 20 7 先序: 3 9 20 15 7 后序: 9 15 7 20 3
1class Rebuild {
2 // 通过先序和中序遍历重建二叉树
3 Node *inpre(int l, int r, int rt, vector<int> &preorder, vector<int> &inorder)
4 {
5 if (l > r) return NULL;
6 int i = l;
7 while (inorder[i] != preorder[rt]) i++;
8 Node *p = new Node(preorder[rt]);
9 p->left = inpre(l, i - 1, rt + 1, preorder, inorder);
10 p->right = inpre(i + 1, r, rt + 1 + i - l, preorder, inorder);
11 return p;
12 }
13
14 // 通过后序和中序遍历重建二叉树
15 Node *inpost(int l, int r, int rt, vector<int> &postorder, vector<int> &inorder)
16 {
17 if (l > r) return nullptr;
18 int i = l;
19 while (inorder[i] != postorder[rt]) ++i;
20 Node *p = new Node(postorder[rt]);
21 p->left = inpost(l, i - 1, rt - 1 - r + i, postorder, inorder);
22 p->right = inpost(i + 1, r, rt - 1, postorder, inorder);
23 return p;
24 }
25
26 Node *deduce(vector<int> &preorder, vector<int> &inorder, vector<int> &postorder)
27 {
28 if (preorder.size()) {
29 return inpre(0, preorder.size() - 1, 0, preorder, inorder);
30 }
31 if (postorder.size()) {
32 return inpost(0, postorder.size() - 1, postorder.size() - 1, postorder, inorder);
33 }
34 return nullptr;
35 }
36};
线索二叉树
二叉树的遍历
1 1
2 / \
3 2 3
4 / \ \
5 4 5 6
6 / \
7 7 8
先序遍历： 1 2 4 5 7 8 3 6 中序遍历： 4 2 7 5 8 1 3 6 后序遍历： 4 7 8 5 2 6 3 1 层次遍历： 1 2 3 4 5 6 7 8
1 A
2 / \
3 B C
4 / / \
5 D E F
6 \ \
7 G H
先序遍历： A B D G C E H F 中序遍历： D G B A E H C F 后序遍历： G D B H E F C A 层次遍历： A B C D E F G H
线索二叉树，将NULL指针指向该遍历方法的前驱和后继结点，构建过程即是遍历过程
对于中序遍历来说，找前驱结点，H是C的前驱，C是H的后继，H是C遍历左子树时访问的最后一个结点，即左子树的“最右下端”结点；找后继结点，A是E的前驱，E是A的后继，E是A遍历右子树时访问的第一个结点，即右子树的“最左下端”结点。