二叉树的前中后序递归法和迭代法
二叉树根据遍历方式，分为深度优先搜索（DFS）和广度优先搜索（BFS）。
二叉树的深度优先搜索：
二叉树的广度优先搜索：
以上二叉树中，深度优先搜索结果：
- 前序遍历（中左右）：1 2 4 5 8 3 6 7 9
- 中序遍历（左中右）：4 2 5 8 1 6 3 9 7
- 后续遍历（左右中）：4 8 5 2 6 9 7 3 1
广度优先搜索结果：
递归法
递归算法三要素：
确定递归的返回值和参数：
确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定递归的终止条件：
操作系统通过栈结构来存储每一层递归的信息，而栈空间是有限的，如果递归没有终止，则会一直递归下去，操作系统的内存栈必然会溢出，导致程序崩溃。
所以何时终止？如何终止？这都是必须要考虑到的。
确定单层递归的处理逻辑：
确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
下面以返回前序遍历的数组举例：
1
2
3
4
5
6
| struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
}
|
确定递归的返回值和参数：要求返回前序遍历的数组，所以递归函数不需要返回值，参数里需要传入二叉树的当前节点和 vector 用于存放遍历的数组。
1
| void preOrder(TreeNode* node, vector<int>& vec)
|
确定递归的终止条件:在递归过程中，为了防止无限递归下去，需要一个终止条件，本例子中，当前节点为空时，不需要（也不能）处理任何信息，所以直接返回就可以了。
确定单层递归的处理逻辑:前序遍历是以中->左->右来进行遍历的，所以优先处理中节点信息，然后再往左节点和右节点递归。
1
2
3
| vec.push_back(node->val);
traversal(node->left, vec);
traversal(node->right, vec);
|
根据以上要素，完成前序遍历的完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
void traversal(TreeNode* node, vector<int>& vec) {
if (!node) return;
vec.push_back(node->val);
traversal(node->left, vec);
traversal(node->right, vec);
}
public:
vector<int> preOrderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
|
根据三要素的思想，不难写出中序遍历和后续遍历，如下：
中序遍历：
1
2
3
4
5
6
7
| void traversal(TreeNode* node, vector<int>& vec) {
if (!node) return;
traversal(node->left, vec);
vec.push_back(node->val);
traversal(node->right, vec);
}
|
后续遍历：
1
2
3
4
5
6
7
| void traversal(TreeNode* node, vector<int>& vec) {
if (!node) return;
traversal(node->left, vec);
traversal(node->right, vec);
vec.push_back(node->val);
}
|
迭代法
递归法的实现就是每一次递归调用都会把函数的局部变量，参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
所以通过栈结构，无需递归也可以实现二叉树的前中后序遍历。
前序遍历
前序遍历就是优先处理中间节点，然后再进行左右节点的处理。所以入栈顺序应该是先压入根节点，接着将右节点压入栈中，再加入左节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<int> preOrderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->right)
st.push(node->right);
if (node->left)
st.push(node->left);
}
return result;
}
};
|
中序遍历
中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进 result 数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<int> midOrderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur || !st.empty()) {
if (cur) {
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
result.push_back(cur->val);
cur = cur->right;
}
}
return result;
}
};
|
后序遍历
前序遍历的遍历顺序是：左右中，后序遍历的顺序是：中左右。
那么我只需要在前序遍历时，将左右中改为右左中，然后再将数组反转（中左右），即可得到后序遍历的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> postOrderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->left)
st.push(node->left);
if (node->right)
st.push(node->right);
}
reverse(result.begin(), result.end());
return result;
}
};
|
迭代方式统一写法
因为迭代法实现的前中后序风格不统一，除了前序和后序有关联，中序完全就是另一种写法了。
针对三种遍历方式，使用迭代法是可以写出统一风格的代码的。
不统一的问题是：无法同时解决访问节点和处理节点不一致的情况。
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢？就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
完整代码如下：
前序遍历
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
| class Solution {
public:
vector<int> preOrderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (!node) {
st.pop();
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
st.push(node);
st.push(nullptr);
} else {
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
|
中序遍历
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
| class Solution {
public:
vector<int> midOrderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (!node) {
st.pop();
if (node->right) st.push(node->right);
st.push(node);
st.push(nullptr);
if (node->left) st.push(node->left);
} else {
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
|
后序遍历
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
| class Solution {
public:
vector<int> postOrderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (!node) {
st.pop();
st.push(node);
st.push(nullptr);
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
} else {
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
|
