-
Notifications
You must be signed in to change notification settings - Fork 13
/
Copy pathSolution0094.java
255 lines (239 loc) · 8.89 KB
/
Solution0094.java
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
// 94. 二叉树的中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
/*
递归思路:
1、定义数据结构:使用列表成员变量,存储每次递归操作存入的值
2、递归终止条件:节点为空时返回
3、单层递归逻辑:把节点的值存入列表
4、递归逻辑:
左右节点需要与根节点做同样的事,就要调同样的方法,即递归
确定递归顺序/遍历顺序,左中右
每层不需要接收使用递归方法返回值,列表成员变量存储了结果
=================================================
新模板注释,递归
节点值加入列表递归函数
1、方法功能:入参是一个节点,将该节点值加入列表,返回列表
2、终止条件:节点为空时,返回列表
3、一个节点处理过程和返回结果:将节点值加入列表,返回列表
4、递归调用:左右节点同样需要加入列表,因此调用同样的方法处理
5、递归顺序:中序遍历,先处理左节点,再处理根节点,最后处理右节点
6、使用递归调用结果和返回结果:不用接收递归调用结果,节点已经加入列表了,直接返回列表即可
* */
class Solution {
public List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return list;
}
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
return list;
}
}
/*
* 递归思路:等同上个实现的逻辑
* */
class Solution {
public List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root != null) {
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
}
return list;
}
}
/*
* 迭代思路:
* 1、定义数据结构:局部变量即可,列表存放结果数据,栈按序存放节点,指针指向下一个要处理的节点
* 2、遍历条件、操作逻辑:
* 当前节点不为空,节点入栈,指向左节点
* 栈不为空,弹出节点,存入节点值,指向右节点
* 3、实现了中序遍历,按序存放节点入栈,按序获取节点值
* */
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
/*
* 迭代思路:等同上个实现的逻辑
* */
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
}
/*
* 1、莫里斯遍历:
* 1)用递归和迭代的方式都使用了辅助的空间,而莫里斯遍历的优点是没有使用任何辅助空间。
* 2)缺点是改变了整个树的结构,强行把一棵二叉树改成一段链表结构。
* 2、思路:把根节点接到左子树的最后一个右节点上,形成链表,再遍历获取链表的值
* 3、相似题:114.二叉树展开为链表,前序遍历
* */
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
while (root != null) {
if (root.left != null) {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root;
TreeNode temp = root;
root = root.left;
temp.left = null;
} else {
list.add(root.val);
root = root.right;
}
}
return list;
}
}
/*
* 迭代思路:
* 1、定义数据结构:结果列表存放排序节点值;节点列表按序存放节点;索引列表存放未判断是否有左右子节点的节点
* 2、数据结构初始化:根节点存入节点列表;索引0存入索引列表
* 3、迭代逻辑:
* 1)索引列表不为空时,说明有节点未判断是否有左右子节点,循环遍历索引列表
* 2)索引列表降序排序,取出最大索引,对该索引的节点进行操作。先处理靠右边的节点,可以防止插入节点时影响了节点列表其他节点的位置
* 3)是否有子节点存在四种情况:有左右节点、只有右节点、只有左节点、没有左右节点。要分别处理,不同情况节点最终索引位置不同
* 4)中序遍历:
* 先插入右节点,再插入左节点
* 插入右节点是在根节点右边插入,其他结点右移一位
* 插入左节点是替代了根节点的位置,根节点和其他结点右移一位
* 5)最大索引的节点判断完左右节点后,移除索引列表的最大索引
* 6)最终节点列表按序排序,遍历结点列表,将节点值存入结果列表
*
* 1
* / \
* 2 3
* / \
* 4 5
* 节点列表:1
* 索引列表:0
* ====================
* 节点列表:2 1 3
* 索引列表:0 2
* ====================
* 节点列表:2 1 4 3 5
* 索引列表:2 5
* ====================
* 节点列表:2 1 4 3 5
* 索引列表:
* */
public class Solution0094 {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
if (root == null) {
return resList;
}
List<TreeNode> nodeList = new ArrayList<>();
List<Integer> indexList = new ArrayList<>();
nodeList.add(root);
indexList.add(0);
while (!indexList.isEmpty()) {
indexList.sort((o1, o2) -> o2 - o1);
int index = indexList.get(0);
root = nodeList.get(index);
if (root.left != null && root.right != null) {
nodeList.add(index + 1, root.right);
nodeList.add(index, root.left);
indexList.add(index + 2);
indexList.add(index);
} else if (root.left != null) {
nodeList.add(index, root.left);
indexList.add(index);
} else if (root.right != null) {
nodeList.add(index + 1, root.right);
indexList.add(index + 1);
}
indexList.remove(0);
}
for (TreeNode node : nodeList) {
resList.add(node.val);
}
return resList;
}
}
/*
* 迭代思路:
* 1、定义数据结构:列表存放节点值;栈按序存放节点;哈希表标记节点是否已处理过左右节点
* 2、数据结构初始化:根节点入栈
* 3、迭代逻辑:
* 1)栈不为空时遍历栈,弹出栈顶节点
* 2)判断当前节点是否已经处理过左右节点,处理过节点值存入列表
* 3)没有则将节点按右中左顺序入栈,弹出时才会是左中右,标记当前节点已处理
* 4、标记目的:节点已经遍历过,但又暂时不能存入列表,所以需要先按序暂存在栈中,按序弹出再存入列表
* 作用与递归相同,递归是使用栈帧保存当前变量,当下一层处理完成后,就可以回到当前栈帧的状态,处理当前的数据
* */
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
if (root == null) {
return resList;
}
Map<TreeNode, Boolean> flagMap = new HashMap<>();
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
root = stack.pop();
if (flagMap.getOrDefault(root, false)) {
resList.add(root.val);
} else {
if (root.right != null) {
stack.push(root.right);
}
stack.push(root);
if (root.left != null) {
stack.push(root.left);
}
flagMap.put(root, true);
}
}
return resList;
}
}