非递归遍历二叉树，其基本思想是借助栈实现二叉树的遍历。本文回顾leetcode上给出的巧妙的一种相同算法解决先序、中序、后序的解法。
基础先序遍历
先序遍历二叉树的顺序为“父节点-左孩子-右孩子”，先给出二叉树的数据结构声明：
1
2
3
4
5
6
7
|
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
|
递归方式先序遍历二叉树：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> rlt;
recursion(root, rlt);
return rlt;
}
void recursion(TreeNode* root, vector<int>& rlt) {
if (!root) {
return;
}
rlt.push_back(root->val);
recursion(root->left, rlt);
recursion(root->right, rlt);
}
};
|
使用栈来迭代遍历二叉树，其基本思想为，每次迭代，栈顶元素出栈，并进行遍历，然后依次将其右孩子、左孩子入栈。
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> preorderTraversal(TreeNode* root) {
vector<int> rlt;
if (!root) {
return rlt;
}
stack<TreeNode*> assist;
assist.push(root);
while (!assist.empty()) {
TreeNode* curNode = assist.top();
assist.pop();
rlt.push_back(curNode->val);
if (curNode->right) {
assist.push(curNode->right);
}
if (curNode->left) {
assist.push(curNode->left);
}
}
return rlt;
}
};
|
分析如何实现统一的先中后遍历算法
仔细考虑先序、中序、后续遍历的区别，它们的区别仅仅在于何时获取元素。
我们用迭代去模拟递归，来实现二叉树的遍历。
用栈遍历二叉树的整体顺序是确定的，我们先访问左子树，后访问右子树，因此右子树先入栈，左子树后入栈，如果不访问节点的话，最简的遍历方式应该是下面这样的：
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:
void Traversal(TreeNode* root) {
if (!root) {
return;
}
stack<TreeNode*> assist;
assist.push(root);
while (!assist.empty()) {
TreeNode* curNode = assist.top();
assist.pop();
if (curNode->right) {
assist.push(curNode->right);
}
if (curNode->left) {
assist.push(curNode->left);
}
}
}
};
|
相当于如下递归代码：
1
2
3
4
5
6
7
8
9
10
| class solution {
public:
void Traversal(TreeNode* root) {
if (!root) {
return;
}
Traversal(root->left);
Traversal(root->right);
}
};
|
我们看到该算法中，只要确定何时获取元素，就可以改造为先序、中序、后序遍历。
- 对于先序遍历而言，先处理父节点，再处理左子树和右子树，其顺序为
父节点-左子树-右子树。
- 对于中序遍历而言，处理父节点时，意味着左子树已全部处理完毕，但右子树尚未处理，其顺序为
左子树-父节点-右子树。
- 对于后序遍历而言，处理父节点时，意味着左右子树都已全部处理完毕，其顺序为
左子树-右子树-父节点。
用栈来处理遍历二叉树问题时，栈顶元素先处理，栈底元素后处理，因此三种遍历方式必须保证栈内元素有如下顺序：
- 先序，父节点在栈顶，然后是左孩子、右孩子。
- 中序，左孩子在栈顶，然后是父节点、右孩子。
- 后序，左孩子在栈顶，然后是右孩子、父节点。
基于以上思路，我们使用一个空节点作为父节点的标记，实现了三种遍历算法。
每遍历一个节点，调整栈顶元素的位置，使其始终保持上述顺序，并在父节点上一层添加空节点进行标记。
当栈顶元素为空节点时，意味着次栈顶元素为需要访问的节点。
改进后的先序遍历
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
| class solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> rlt;
if (!root) {
return rlt;
}
stack<TreeNode*> assist;
assist.push(root);
while (!assist.empty()) {
TreeNode* curNode = assist.top();
assist.pop();
if (curNode) {
if (curNode->right) {
assist.push(curNode->right);
}
if (curNode->left) {
assist.push(curNode->left);
}
assist.push(curNode);
assist.push(nullptr);
}
else {
rlt.push_back(assist.top()->val);
assist.pop();
}
}
return rlt;
}
};
|
改进后的中序遍历
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
| class solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> rlt;
if (!root) {
return rlt;
}
stack<TreeNode*> assist;
assist.push(root);
while (!assist.empty()) {
TreeNode* curNode = assist.top();
assist.pop();
if (curNode) {
if (curNode->right) {
assist.push(curNode->right);
}
assist.push(curNode);
assist.push(nullptr);
if (curNode->left) {
assist.push(curNode->left);
}
}
else {
rlt.push_back(assist.top()->val);
assist.pop();
}
}
return rlt;
}
};
|
改进后的后序遍历
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
| class solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> rlt;
if (!root) {
return rlt;
}
stack<TreeNode*> assist;
assist.push(root);
while (!assist.empty()) {
TreeNode* curNode = assist.top();
assist.pop();
if (curNode) {
assist.push(curNode);
assist.push(nullptr);
if (curNode->right) {
assist.push(curNode->right);
}
if (curNode->left) {
assist.push(curNode->left);
}
}
else {
rlt.push_back(assist.top()->val);
assist.pop();
}
}
return rlt;
}
};
|
