Skip to content

Commit f63d563

Browse files
melody-limelody-li
authored
Merge pull request algorithm004-01#390 from aseara/master
466-Week 02
2 parents c4d447a + c296c57 commit f63d563

11 files changed

+1484
-0
lines changed

‎Week 02/id_466/LeetCode_144_466.java‎

Lines changed: 194 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,194 @@
1+
//给定一个二叉树，返回它的 前序 遍历。
2+
//
3+
// 示例:
4+
//
5+
// 输入: [1,null,2,3]
6+
// 1
7+
// \
8+
// 2
9+
// /
10+
// 3
11+
//
12+
//输出: [1,2,3]
13+
//
14+
//
15+
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
16+
// Related Topics 栈 树
17+
package com.aseara.leetcode.editor.cn.a144;
18+
19+
import org.junit.jupiter.api.Test;
20+
21+
import java.util.Arrays;
22+
import java.util.LinkedList;
23+
import java.util.List;
24+
25+
import static org.junit.jupiter.api.Assertions.assertIterableEquals;
26+
27+
/**
28+
* desc: 144.二叉树的前序遍历 <br />
29+
* Date: 2019/10/24 <br/>
30+
*
31+
* @author qiujingde
32+
*/
33+
class BinaryTreePreorderTraversal {
34+
private Solution solution = new Solution();
35+
36+
@Test
37+
void test1() {
38+
TreeNode root = new TreeNode(1);
39+
TreeNode child = new TreeNode(2);
40+
root.right = child;
41+
child.left = new TreeNode(3);
42+
43+
List<Integer> expected = Arrays.asList(1, 2, 3);
44+
assertIterableEquals(expected, solution.preorderTraversal(root));
45+
}
46+
47+
}
48+
49+
class TreeNode {
50+
int val;
51+
TreeNode left;
52+
TreeNode right;
53+
TreeNode(int x) { val = x; }
54+
}
55+
56+
//leetcode submit region begin(Prohibit modification and deletion)
57+
/**
58+
* Definition for a binary tree node.
59+
* public class TreeNode {
60+
* int val;
61+
* TreeNode left;
62+
* TreeNode right;
63+
* TreeNode(int x) { val = x; }
64+
* }
65+
*/
66+
class Solution {
67+
public List<Integer> preorderTraversal(TreeNode root) {
68+
List<Integer> store = new LinkedList<>();
69+
traversal5(root, store);
70+
return store;
71+
}
72+
73+
private void traversal(TreeNode root, List<Integer> store) {
74+
if (root == null) {
75+
return;
76+
}
77+
store.add(root.val);
78+
traversal(root.left, store);
79+
traversal(root.right, store);
80+
}
81+
82+
private void traversal2(TreeNode root, List<Integer> store) {
83+
if (root == null) {
84+
return;
85+
}
86+
87+
LinkedList<TreeNode> stack = new LinkedList<>();
88+
stack.push(root);
89+
store.add(root.val);
90+
91+
while (!stack.isEmpty()) {
92+
TreeNode node = stack.peek();
93+
while (node.left != null) {
94+
stack.push(node.left);
95+
store.add(node.left.val);
96+
node = node.left;
97+
}
98+
99+
node = stack.pop();
100+
while (!stack.isEmpty() && node.right == null) {
101+
node = stack.pop();
102+
}
103+
104+
if (node.right != null) {
105+
stack.push(node.right);
106+
store.add(node.right.val);
107+
}
108+
}
109+
110+
}
111+
112+
private void traversal3(TreeNode root, List<Integer> store) {
113+
if (root == null) {
114+
return;
115+
}
116+
117+
LinkedList<TreeNode> stack = new LinkedList<>();
118+
stack.push(root);
119+
120+
while (!stack.isEmpty()) {
121+
TreeNode cur = stack.pop();
122+
store.add(cur.val);
123+
if (cur.right != null) {
124+
stack.push(cur.right);
125+
}
126+
if (cur.left != null) {
127+
stack.push(cur.left);
128+
}
129+
}
130+
}
131+
132+
private void traversal4(TreeNode root, List<Integer> store) {
133+
if (root == null) {
134+
return;
135+
}
136+
TreeNode cur = root;
137+
138+
while (cur != null) {
139+
store.add(cur.val);
140+
if (cur.left == null) {
141+
cur = cur.right;
142+
continue;
143+
}
144+
if (cur.right != null) {
145+
TreeNode pre = cur.left;
146+
while (pre.right != null) {
147+
pre = pre.right;
148+
}
149+
pre.right = cur.right;
150+
}
151+
cur = cur.left;
152+
}
153+
}
154+
155+
private enum CommandCode {
156+
READ, TRAVERSAL
157+
}
158+
159+
private static class Command {
160+
CommandCode code;
161+
TreeNode node;
162+
Command(CommandCode code, TreeNode node) {
163+
this.code = code;
164+
this.node = node;
165+
}
166+
}
167+
168+
private void traversal5(TreeNode root, List<Integer> store) {
169+
if (root == null) {
170+
return;
171+
}
172+
LinkedList<Command> stack = new LinkedList<>();
173+
stack.push(new Command(CommandCode.TRAVERSAL, root));
174+
while (!stack.isEmpty()) {
175+
Command command = stack.pop();
176+
TreeNode node = command.node;
177+
switch (command.code) {
178+
case READ:
179+
store.add(node.val);
180+
break;
181+
case TRAVERSAL:
182+
if (node.right != null) {
183+
stack.push(new Command(CommandCode.TRAVERSAL, node.right));
184+
}
185+
if (node.left != null) {
186+
stack.push(new Command(CommandCode.TRAVERSAL, node.left));
187+
}
188+
stack.push(new Command(CommandCode.READ, node));
189+
}
190+
}
191+
}
192+
193+
}
194+
//leetcode submit region end(Prohibit modification and deletion)

‎Week 02/id_466/LeetCode_145_466.java‎

Lines changed: 195 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,195 @@
1+
//给定一个二叉树，返回它的 后序 遍历。
2+
//
3+
// 示例:
4+
//
5+
// 输入: [1,null,2,3]
6+
// 1
7+
// \
8+
// 2
9+
// /
10+
// 3
11+
//
12+
//输出: [3,2,1]
13+
//
14+
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
15+
// Related Topics 栈 树
16+
package com.aseara.leetcode.editor.cn.a145;
17+
18+
import org.junit.jupiter.api.Test;
19+
20+
import java.util.Arrays;
21+
import java.util.LinkedList;
22+
import java.util.List;
23+
24+
import static org.junit.jupiter.api.Assertions.assertIterableEquals;
25+
26+
/**
27+
* desc: 145.二叉树的后序遍历 <br />
28+
* Date: 2019/10/24 <br/>
29+
*
30+
* @author qiujingde
31+
*/
32+
class BinaryTreePostorderTraversal {
33+
private Solution solution = new Solution();
34+
35+
@Test
36+
void test1() {
37+
TreeNode root = new TreeNode(1);
38+
TreeNode child = new TreeNode(2);
39+
root.right = child;
40+
child.left = new TreeNode(3);
41+
42+
List<Integer> expected = Arrays.asList(3, 2, 1);
43+
assertIterableEquals(expected, solution.postorderTraversal(root));
44+
}
45+
46+
}
47+
48+
class TreeNode {
49+
int val;
50+
TreeNode left;
51+
TreeNode right;
52+
TreeNode(int x) { val = x; }
53+
}
54+
55+
//leetcode submit region begin(Prohibit modification and deletion)
56+
/**
57+
* Definition for a binary tree node.
58+
* public class TreeNode {
59+
* int val;
60+
* TreeNode left;
61+
* TreeNode right;
62+
* TreeNode(int x) { val = x; }
63+
* }
64+
*/
65+
class Solution {
66+
public List<Integer> postorderTraversal(TreeNode root) {
67+
LinkedList<Integer> store = new LinkedList<>();
68+
traversal3(root, store);
69+
return store;
70+
}
71+
72+
private void traversal(TreeNode root, List<Integer> store) {
73+
if (root == null) {
74+
return;
75+
}
76+
traversal(root.left, store);
77+
traversal(root.right, store);
78+
store.add(root.val);
79+
}
80+
81+
private void traversal2(TreeNode root, List<Integer> store) {
82+
if (root == null) {
83+
return;
84+
}
85+
LinkedList<TreeNode> stack = new LinkedList<>();
86+
LinkedList<Boolean> direction = new LinkedList<>();
87+
88+
stack.push(root);
89+
90+
while (!stack.isEmpty()) {
91+
TreeNode node = stack.peek();
92+
while (node.left != null) {
93+
stack.push(node.left);
94+
direction.push(true);
95+
node = node.left;
96+
}
97+
98+
boolean r = true;
99+
while (!r || node.right == null) {
100+
node = stack.pop();
101+
store.add(node.val);
102+
if (stack.isEmpty()) {
103+
return;
104+
}
105+
node = stack.peek();
106+
r = direction.pop();
107+
}
108+
109+
stack.push(node.right);
110+
direction.push(false);
111+
}
112+
}
113+
114+
private void traversal3(TreeNode root, LinkedList<Integer> store) {
115+
if (root == null) {
116+
return;
117+
}
118+
LinkedList<TreeNode> stack = new LinkedList<>();
119+
stack.push(root);
120+
121+
while (!stack.isEmpty()) {
122+
TreeNode node = stack.pop();
123+
store.addFirst(node.val);
124+
125+
if (node.left != null) {
126+
stack.push(node.left);
127+
}
128+
if (node.right != null) {
129+
stack.push(node.right);
130+
}
131+
}
132+
}
133+
134+
private void traversal4(TreeNode root, LinkedList<Integer> store) {
135+
if (root == null) {
136+
return;
137+
}
138+
TreeNode cur = root;
139+
while (cur != null) {
140+
store.addFirst(cur.val);
141+
if (cur.right == null) {
142+
cur = cur.left;
143+
continue;
144+
}
145+
if (cur.left != null) {
146+
TreeNode pre = cur.right;
147+
while (pre.left != null) {
148+
pre = pre.left;
149+
}
150+
pre.left = cur.left;
151+
}
152+
cur = cur.right;
153+
}
154+
}
155+
156+
private enum CommandCode {
157+
READ, TRAVERSAL
158+
}
159+
160+
private static class Command {
161+
CommandCode code;
162+
TreeNode node;
163+
Command(CommandCode code, TreeNode node) {
164+
this.code = code;
165+
this.node = node;
166+
}
167+
}
168+
169+
private void traversal5(TreeNode root, List<Integer> store) {
170+
if (root == null) {
171+
return;
172+
}
173+
LinkedList<Command> stack = new LinkedList<>();
174+
stack.push(new Command(CommandCode.TRAVERSAL, root));
175+
while (!stack.isEmpty()) {
176+
Command command = stack.pop();
177+
TreeNode node = command.node;
178+
switch (command.code) {
179+
case READ:
180+
store.add(node.val);
181+
break;
182+
case TRAVERSAL:
183+
stack.push(new Command(CommandCode.READ, node));
184+
if (node.right != null) {
185+
stack.push(new Command(CommandCode.TRAVERSAL, node.right));
186+
}
187+
if (node.left != null) {
188+
stack.push(new Command(CommandCode.TRAVERSAL, node.left));
189+
}
190+
}
191+
}
192+
}
193+
194+
}
195+
//leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)