Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita3a02ad

Browse files
Update
1 parent4aea708 commita3a02ad

File tree

2 files changed

+277
-0
lines changed

2 files changed

+277
-0
lines changed
Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
2+
>统一写法是一种什么感觉
3+
4+
此时我们在[二叉树：一入递归深似海，从此offer是路人](https://mp.weixin.qq.com/s/PwVIfxDlT3kRgMASWAMGhA)中用递归的方式，实现了二叉树前中后序的遍历。
5+
6+
在[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)中用栈实现了二叉树前后中序的迭代遍历（非递归）。
7+
8+
之后我们发现**迭代法实现的先中后序，其实风格也不是那么统一，除了先序和后序，有关联，中序完全就是另一个风格了，一会用栈遍历，一会又用指针来遍历。**
9+
10+
实践过的同学，也会发现使用迭代法实现先中后序遍历，很难写出统一的代码，不像是递归法，实现了其中的一种遍历方式，其他两种只要稍稍改一下节点顺序就可以了。
11+
12+
其实**针对三种遍历方式，使用迭代法是可以写出统一风格的代码！**
13+
14+
**重头戏来了，接下来介绍一下统一写法。**
15+
16+
我们以中序遍历为例，在[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)中提到说使用栈的话，**无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况**。
17+
18+
**那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。**
19+
20+
如何标记呢，**就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。** 这种方法也可以叫做标记法。
21+
22+
#迭代法中序遍历
23+
24+
中序遍历代码如下：（详细注释）
25+
26+
```
27+
class Solution {
28+
public:
29+
vector<int> inorderTraversal(TreeNode* root) {
30+
vector<int> result;
31+
stack<TreeNode*> st;
32+
if (root != NULL) st.push(root);
33+
while (!st.empty()) {
34+
TreeNode* node = st.top();
35+
if (node != NULL) {
36+
st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
37+
if (node->right) st.push(node->right); // 添加右节点（空节点不入栈）
38+
39+
st.push(node); // 添加中节点
40+
st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。
41+
42+
if (node->left) st.push(node->left); // 添加左节点（空节点不入栈）
43+
} else { // 只有遇到空节点的时候，才将下一个节点放进结果集
44+
st.pop(); // 将空节点弹出
45+
node = st.top(); // 重新取出栈中元素
46+
st.pop();
47+
result.push_back(node->val); // 加入到结果集
48+
}
49+
}
50+
return result;
51+
}
52+
};
53+
```
54+
55+
看代码有点抽象我们来看一下动画(中序遍历)：
56+
57+
<videosrc='../video/中序遍历迭代（统一写法）.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
58+
59+
动画中，result数组就是最终结果集。
60+
61+
可以看出我们将访问的节点直接加入到栈中，但如果是处理的节点则后面放入一个空节点， 这样只有空节点弹出的时候，才将下一个节点放进结果集。
62+
63+
此时我们再来看前序遍历代码。
64+
65+
#迭代法前序遍历
66+
67+
迭代法前序遍历代码如下： (**注意此时我们和中序遍历相比仅仅改变了两行代码的顺序**)
68+
69+
```
70+
class Solution {
71+
public:
72+
vector<int> preorderTraversal(TreeNode* root) {
73+
vector<int> result;
74+
stack<TreeNode*> st;
75+
if (root != NULL) st.push(root);
76+
while (!st.empty()) {
77+
TreeNode* node = st.top();
78+
if (node != NULL) {
79+
st.pop();
80+
if (node->right) st.push(node->right); // 右
81+
if (node->left) st.push(node->left); // 左
82+
st.push(node); // 中
83+
st.push(NULL);
84+
} else {
85+
st.pop();
86+
node = st.top();
87+
st.pop();
88+
result.push_back(node->val);
89+
}
90+
}
91+
return result;
92+
}
93+
};
94+
```
95+
96+
#迭代法后序遍历
97+
98+
后续遍历代码如下： (**注意此时我们和中序遍历相比仅仅改变了两行代码的顺序**)
99+
100+
```
101+
class Solution {
102+
public:
103+
vector<int> postorderTraversal(TreeNode* root) {
104+
vector<int> result;
105+
stack<TreeNode*> st;
106+
if (root != NULL) st.push(root);
107+
while (!st.empty()) {
108+
TreeNode* node = st.top();
109+
if (node != NULL) {
110+
st.pop();
111+
st.push(node); // 中
112+
st.push(NULL);
113+
114+
if (node->right) st.push(node->right); // 右
115+
if (node->left) st.push(node->left); // 左
116+
117+
} else {
118+
st.pop();
119+
node = st.top();
120+
st.pop();
121+
result.push_back(node->val);
122+
}
123+
}
124+
return result;
125+
}
126+
};
127+
```
128+
129+
#总结
130+
131+
此时我们写出了统一风格的迭代法，不用在纠结于前序写出来了，中序写不出来的情况了。
132+
133+
但是统一风格的迭代法并不好理解，而且想在面试直接写出来还有难度的。
134+
135+
所以大家根据自己的个人喜好，对于二叉树的前中后序遍历，选择一种自己容易理解的递归和迭代法。
136+

‎problems/二叉树的迭代遍历.md

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
>听说还可以用非递归的方式
2+
3+
看完本篇大家可以使用迭代法，再重新解决如下三道leetcode上的题目：
4+
5+
* 144.二叉树的前序遍历
6+
* 94.二叉树的中序遍历
7+
* 145.二叉树的后序遍历
8+
9+
为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？
10+
11+
我们在[栈与队列：匹配问题都是栈的强项](https://mp.weixin.qq.com/s/eynAEbUbZoAWrk0ZlEugqg)中提到了，**递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中**，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
12+
13+
此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。
14+
15+
##前序遍历（迭代法）
16+
17+
我们先看一下前序遍历。
18+
19+
前序遍历是中左右，每次先处理的是中间节点，那么先将跟节点放入栈中，然后将右孩子加入栈，再加入左孩子。
20+
21+
为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
22+
23+
动画如下：
24+
25+
<imgsrc='../video/二叉树前序遍历（迭代法）.gif'width=600> </img></div>
26+
27+
不难写出如下代码: （**注意代码中空节点不入栈**）
28+
29+
```
30+
class Solution {
31+
public:
32+
vector<int> preorderTraversal(TreeNode* root) {
33+
stack<TreeNode*> st;
34+
vector<int> result;
35+
if (root == NULL) return result;
36+
st.push(root);
37+
while (!st.empty()) {
38+
TreeNode* node = st.top(); // 中
39+
st.pop();
40+
result.push_back(node->val);
41+
if (node->right) st.push(node->right); // 右（空节点不入栈）
42+
if (node->left) st.push(node->left); // 左（空节点不入栈）
43+
}
44+
return result;
45+
}
46+
};
47+
```
48+
49+
此时会发现貌似使用迭代法写出前序遍历并不难，确实不难。
50+
51+
**此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了？**
52+
53+
其实还真不行！
54+
55+
但接下来，**再用迭代法写中序遍历的时候，会发现套路又不一样了，目前的前序遍历的逻辑无法直接应用到中序遍历上。**
56+
57+
##中序遍历（迭代法）
58+
59+
为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：
60+
61+
1.**处理：将元素放进result数组中**
62+
2.**访问：遍历节点**
63+
64+
分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，**因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。**
65+
66+
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了**处理顺序和访问顺序是不一致的。**
67+
68+
那么**在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。**
69+
70+
动画如下：
71+
72+
<imgsrc='../video/二叉树中序遍历（迭代法）.gif'width=600> </img></div>
73+
74+
**中序遍历，可以写出如下代码：**
75+
76+
```
77+
class Solution {
78+
public:
79+
vector<int> inorderTraversal(TreeNode* root) {
80+
vector<int> result;
81+
stack<TreeNode*> st;
82+
TreeNode* cur = root;
83+
while (cur != NULL || !st.empty()) {
84+
if (cur != NULL) { // 指针来访问节点，访问到最底层
85+
st.push(cur); // 将访问的节点放进栈
86+
cur = cur->left; // 左
87+
} else {
88+
cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
89+
st.pop();
90+
result.push_back(cur->val); // 中
91+
cur = cur->right; // 右
92+
}
93+
}
94+
return result;
95+
}
96+
};
97+
98+
```
99+
100+
##后序遍历（迭代法）
101+
102+
再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
103+
104+
![前序到后序](https://img-blog.csdnimg.cn/20200808200338924.png)
105+
106+
**所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：**
107+
108+
```
109+
class Solution {
110+
public:
111+
vector<int> postorderTraversal(TreeNode* root) {
112+
stack<TreeNode*> st;
113+
vector<int> result;
114+
if (root == NULL) return result;
115+
st.push(root);
116+
while (!st.empty()) {
117+
TreeNode* node = st.top();
118+
st.pop();
119+
result.push_back(node->val);
120+
if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
121+
if (node->right) st.push(node->right); // 空节点不入栈
122+
}
123+
reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
124+
return result;
125+
}
126+
};
127+
128+
```
129+
130+
#总结
131+
132+
此时我们用迭代法写出了二叉树的前后中序遍历，大家可以看出前序和中序是完全两种代码风格，并不想递归写法那样代码稍做调整，就可以实现前后中序。
133+
134+
**这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！**
135+
136+
上面这句话，可能一些同学不太理解，建议自己亲手用迭代法，先写出来前序，再试试能不能写出中序，就能理解了。
137+
138+
**那么问题又来了，难道 二叉树前后中序遍历的迭代法实现，就不能风格统一么（即前序遍历 改变代码顺序就可以实现中序 和 后序）？**
139+
140+
当然可以，这种写法，还不是很好理解，我们将在下一篇文章里重点讲解，敬请期待！
141+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp