本文于 2023-08-18 更新中序遍历的 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
| class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
ans.push_back(cur->val);
if (cur->right != nullptr) {
st.push(cur->right);
}
if (cur->left != nullptr) {
st.push(cur->left);
}
}
return ans;
}
};
|
实现 2⭐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == NULL) {
return ans;
}
TreeNode* cur = root;
stack<TreeNode*> st;
while (cur || !st.empty()) {
if (cur) {
ans.push_back(cur->val);
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
cur = cur->right;
}
}
return ans;
}
};
|
中序遍历 左根右
实现 1
- 沿着当前节点的左链不断入栈，直到找不到新的左子节点
- 栈顶节点出栈并访问，如果该节点右子节点不为空，那么将该节点右节点入栈，将当前节点改为该节点的右子节点，重复 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
| class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
stack<TreeNode*> st;
auto cur = root;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push(cur);
cur = cur->left;
}
auto head = st.top();
st.pop();
ans.push_back(head->val);
if (head->right != nullptr) {
cur = head->right;
} else {
cur = nullptr;
}
}
return ans;
}
};
|
实现 2⭐
相同的思路，更简洁的实现（来源于王道书）。
注意与前序遍历的实现 2 对比，会发现仅仅是加入 ans 的语句的位置不同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == NULL) {
return ans;
}
TreeNode* cur = root;
stack<TreeNode*> st;
while (cur || !st.empty()) {
if (cur) {
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
ans.push_back(cur->val);
cur = cur->right;
}
}
return ans;
}
};
|
Ref:
Inorder Tree Traversal without Recursion - GeeksforGeeks
后序遍历 左右根
实现 0
仅从解题的角度来说，一种解法是，在前序遍历的实现 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
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
auto cur = st.top();
st.pop();
ans.push_back(cur->val);
if (cur->left != nullptr) {
st.push(cur->left);
}
if (cur->right != nullptr) {
st.push(cur->right);
}
}
reverse(ans.begin(), ans.end());
return ans;
}
};
|
但是这并不是真正意义上的后序遍历。
实现 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
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == NULL) {
return ans;
}
stack<TreeNode*> st;
while (1) {
while (root != NULL) {
st.push(root);
st.push(root);
root = root->left;
}
if (st.empty()) {
return ans;
}
root = st.top();
st.pop();
if (!st.empty() && root == st.top()) {
root = root->right;
} else {
ans.push_back(root->val);
root = NULL;
}
}
return ans;
}
};
|
实现 2⭐
一路向左走直至没有左子节点了。对于当前节点，如果其右子节点为空或是已经被访问了，那么可以对其进行访问；否则，对其右子节点执行以上操作。对于如何判断「已经被访问」，我们又有两种思路。
使用一个哈希表记录已经被访问的节点：
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
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == NULL) {
return ans;
}
stack<TreeNode*> st;
unordered_set<TreeNode*> s;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
if (cur->right == NULL || s.find(cur->right) != s.end()) {
ans.push_back(cur->val);
s.insert(cur);
cur = NULL;
} else {
st.push(cur);
cur = cur->right;
}
}
}
return ans;
}
};
|
增加一个额外的指针 pre，记录上一次被访问到的节点
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
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == NULL) {
return ans;
}
stack<TreeNode*> st;
TreeNode* pre = NULL;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
if (cur->right == NULL || pre == cur->right) {
ans.push_back(cur->val);
pre = cur;
cur = NULL;
} else {
st.push(cur);
cur = cur->right;
}
}
}
return ans;
}
};
|
Ref:
- Iterative Postorder Traversal | Set 2 (Using One Stack) - GeeksforGeeks
- 王道论坛数据结构考研复习指导
实现 3
非栈非递归，使用哈希表
我们知道，在后序遍历中，只有当根节点的左子节点和右子节点均被访问后，才可以访问根节点。
使用一个哈希集合来记录一个节点是否被访问
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
unordered_set<TreeNode*> set;
TreeNode* tmp = root;
while (root != nullptr && set.find(tmp) == set.end()) {
if (tmp->left != nullptr && set.find(tmp->left) == set.end()) {
tmp = tmp->left;
} else if (tmp->right != nullptr && set.find(tmp->right) == set.end()) {
tmp = tmp->right;
} else {
ans.push_back(tmp->val);
set.insert(tmp);
tmp = root;
}
}
return ans;
}
};
|
在本方法中，任何一个节点被输出后即马上返回根节点。这是因为在普通的二叉树中无法从子节点直接回到父节点。那么想要在左右子节点均被访问后再访问父节点，只能回到根节点再往下走了。
这种方法效率是较低的。
Ref:
Postorder traversal of Binary Tree without recursion and without stack - GeeksforGeeks
中序遍历的 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
| vector<int> morrisInorderTraversal(TreeNode *root) {
vector<int> ans;
TreeNode *cur = root;
TreeNode *pre = nullptr;
while (cur != nullptr) {
if (cur->left == nullptr) {
ans.push_back(cur->val);
cur = cur->right;
} else {
pre = cur->left;
while (pre->right != nullptr && pre->right != cur) {
pre = pre->right;
}
if (pre->right == nullptr) {
pre->right = cur;
cur = cur->left;
} else {
ans.push_back(cur->val);
pre->right = nullptr;
cur = cur->right;
}
}
}
}
|