-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathSolution0144.java
More file actions
234 lines (218 loc) · 8.54 KB
/
Copy pathSolution0144.java
File metadata and controls
234 lines (218 loc) · 8.54 KB
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
// 144. 二叉树的前序遍历
/**
* 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> preorderTraversal(TreeNode root) {
if (root == null) {
return list;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
}
/*
递归思路：分解问题计算出答案。通过维护局部变量，存放子问题的结果，将子结果返回给上一层使用，层层累计处理，得到最终结果
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
res.add(root.val);
res.addAll(preorderTraversal(root.left));
res.addAll(preorderTraversal(root.right));
return res;
}
}
/*
* 迭代思路：
* 1、定义数据结构：局部变量即可，列表存放结果数据，栈按序存放节点，指针指向下一个要处理的节点
* 2、遍历条件、操作逻辑：
* 如果当前节点为空，则从栈弹出节点
* 存入当前节点值；右节点入栈，用来后面获取右节点的值；指向左节点
* */
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur == null) {
cur = stack.pop();
}
list.add(cur.val);
if (cur.right != null) {
stack.push(cur.right);
}
cur = cur.left;
}
return list;
}
}
/*
* 迭代思路：
* 1、定义数据结构：局部变量即可，列表存放结果数据，栈按序存放节点，指针指向下一个要处理的节点
* 2、遍历条件、操作逻辑：
* 存入当前节点值；当前节点入栈，用来后面获取右节点；指向左节点
* */
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
list.add(cur.val);
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
cur = cur.right;
}
return list;
}
}
/*
* 迭代思路：
* 1、定义数据结构：局部变量即可，列表存放结果数据，栈按序存放节点
* 2、遍历条件、操作逻辑：
* 存入当前节点值；右节点入栈；左节点入栈
* 3、用左节点入栈弹出的方式代替了指针标记下一个要处理的节点
* */
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
return list;
}
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
if (root.right != null) {
stack.push(root.right);
}
if (root.left != null) {
stack.push(root.left);
}
}
return list;
}
}
/*
* 迭代思路：
* 1、定义数据结构：结果列表存放排序节点值；节点列表按序存放节点；索引列表存放未判断是否有左右子节点的节点
* 2、数据结构初始化：根节点存入节点列表；索引0存入索引列表
* 3、迭代逻辑：
* 1）索引列表不为空时，说明有节点未判断是否有左右子节点，循环遍历索引列表
* 2）索引列表降序排序，取出最大索引，对该索引的节点进行操作。先处理靠右边的节点，可以防止插入节点时影响了节点列表其他节点的位置
* 3）是否有子节点存在四种情况：有左右节点、只有右节点、只有左节点、没有左右节点。要分别处理，不同情况节点最终索引位置不同
* 4）前序遍历：
* 先插入右节点，再插入左节点
* 插入左右节点都是在根节点右边插入，其他结点右移一位
* 5）最大索引的节点判断完左右节点后，移除索引列表的最大索引
* 6）最终节点列表按序排序，遍历结点列表，将节点值存入结果列表
* */
class Solution {
public List<Integer> preorderTraversal(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 + 1, root.left);
indexList.add(index + 2);
indexList.add(index + 1);
} else if (root.left != null) {
nodeList.add(index + 1, root.left);
indexList.add(index + 1);
} 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、节点连接步骤：
* 1）前序遍历是中左右，即根节点→左子树→右子树
* 2）左子树遍历的最后一个节点是 左子树的最后一个右子节点，因此要将其连接到根节点的右节点上
* 3）根节点的右指针要指向左节点，左指针指向空，从而形成中左右的链表
* 2、遍历逻辑：
* 1）根指针的移动代表着前序遍历的顺序，循环遍历条件是根指针不为空
* 2）如果根节点的左节点不为空，则进行节点连接步骤；如果为空，则将节点值存入列表，根指针指向右节点
* 3、“114.二叉树展开为链表”的解法
* */
class Solution {
public List<Integer> flatten(TreeNode root) {
List<Integer> list = new ArrayList<>();
while (root != null) {
if (root.left != null) {
TreeNode temp = root.left;
while (temp.right != null) {
temp = temp.right;
}
temp.right = root.right;
root.right = root.left;
root.left = null;
} else {
list.add(root.val);
root = root.right;
}
}
return list;
}
}