Skip to content

Commit 36bb081

Browse files
author
chenweijie
committed
add study/test/solution
1 parent 0aa1109 commit 36bb081

File tree

27 files changed

+780
-23
lines changed

27 files changed

+780
-23
lines changed

‎src/main/java/com/chen/algorithm/exercise/tree/traverseTree/LevelTraverseTree.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -82,7 +82,7 @@ public List<List<Integer>> levelOrder2(TreeNode root) {
8282
// number of elements in the current level
8383
int level_length = queue.size();
8484
for (int i = 0; i < level_length; ++i) {
85-
TreeNode TreeNode = queue.remove();
85+
TreeNode TreeNode = queue.poll();
8686

8787
// fulfill the current level
8888
levels.get(level).add(TreeNode.val);

‎src/main/java/com/chen/algorithm/exercise/tree/traverseTree/PostorderTraversal.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66

77
/**
88
* https://leetcode-cn.com/problems/binary-tree-postorder-traversal/ 145
9-
* 先序遍历
9+
* 后续遍历
1010
* <p>
1111
* <p>
1212
* https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/

‎src/main/java/com/chen/algorithm/study/test102/Solution.java

Lines changed: 21 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,9 @@
11
package com.chen.algorithm.study.test102;
22

33
import java.util.ArrayList;
4-
import java.util.Arrays;
4+
import java.util.LinkedList;
55
import java.util.List;
6+
import java.util.Queue;
67

78
/**
89
* @author : chen weijie
@@ -23,30 +24,30 @@ class TreeNode {
2324

2425

2526
public List<List<Integer>> levelOrder(TreeNode root) {
26-
2727
if (root == null) {
28-
return null;
28+
return new ArrayList<>();
2929
}
3030

31-
3231
List<List<Integer>> result = new ArrayList<>();
33-
34-
result.add(Arrays.asList(root.val));
35-
36-
37-
while (root.left!=null||root.right!=null){
38-
39-
List<Integer> list = new ArrayList<>();
40-
41-
42-
43-
32+
Queue<TreeNode> queue = new LinkedList<>();
33+
queue.add(root);
34+
while (!queue.isEmpty()) {
35+
int size = queue.size();
36+
ArrayList<Integer> arrayList = new ArrayList<>();
37+
38+
for (int i = 0; i < size; i++) {
39+
TreeNode temp = queue.poll();
40+
arrayList.add(temp.val);
41+
if (temp.left != null) {
42+
queue.add(temp.left);
43+
}
44+
if (temp.right != null) {
45+
queue.add(temp.right);
46+
}
47+
}
48+
result.add(arrayList);
4449
}
45-
46-
47-
48-
49-
return null;
50+
return result;
5051
}
5152

5253

‎src/main/java/com/chen/algorithm/study/test102/Solution2.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.chen.algorithm.study.test102;
2+
3+
import java.util.List;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2020-05-11 23:01
8+
*/
9+
public class Solution2 {
10+
11+
12+
public class TreeNode {
13+
int val;
14+
TreeNode left;
15+
TreeNode right;
16+
17+
TreeNode(int x) {
18+
val = x;
19+
}
20+
}
21+
22+
23+
public List<List<Integer>> levelOrder(TreeNode root) {
24+
25+
26+
27+
return null;
28+
}
29+
30+
31+
32+
33+
34+
35+
36+
37+
}

‎src/main/java/com/chen/algorithm/study/test104/Solution2.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.chen.algorithm.study.test104;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* @author : chen weijie
8+
* @Date: 2020-05-17 01:09
9+
*/
10+
public class Solution2 {
11+
12+
13+
public int maxDepth(TreeNode root) {
14+
15+
if (root == null) {
16+
return 0;
17+
}
18+
19+
Queue<TreeNode> queue = new LinkedList<>();
20+
queue.add(root);
21+
22+
int maxDepth = 0;
23+
while (!queue.isEmpty()) {
24+
maxDepth++;
25+
26+
int length = queue.size();
27+
for (int i = 0; i < length; i++) {
28+
TreeNode node = queue.poll();
29+
30+
if (node.left != null) {
31+
queue.add(node.left);
32+
}
33+
34+
if (node.right != null) {
35+
queue.add(node.right);
36+
}
37+
}
38+
}
39+
return maxDepth;
40+
}
41+
}

‎src/main/java/com/chen/algorithm/study/test111/Solution.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.chen.algorithm.study.test111;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* @author : chen weijie
8+
* @Date: 2020-05-17 01:17
9+
*/
10+
public class Solution {
11+
12+
public int minDepth(TreeNode root) {
13+
14+
if (root == null) {
15+
return 0;
16+
}
17+
18+
Queue<TreeNode> queue = new LinkedList<>();
19+
queue.add(root);
20+
21+
int minDepth = 0;
22+
while (!queue.isEmpty()) {
23+
minDepth++;
24+
25+
int length = queue.size();
26+
for (int i = 0; i < length; i++) {
27+
TreeNode node = queue.poll();
28+
29+
if (node.left != null) {
30+
queue.add(node.left);
31+
}
32+
33+
if (node.right != null) {
34+
queue.add(node.right);
35+
}
36+
37+
if (node.left == null && node.right == null) {
38+
return minDepth;
39+
}
40+
}
41+
}
42+
return minDepth;
43+
}
44+
45+
46+
}

‎src/main/java/com/chen/algorithm/study/test111/Solution2.java

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package com.chen.algorithm.study.test111;
2+
3+
4+
/**
5+
* @author : chen weijie
6+
* @Date: 2020-05-17 01:09
7+
*/
8+
public class Solution2 {
9+
10+
11+
public int minDepth(TreeNode root) {
12+
13+
if (root == null) {
14+
return 0;
15+
}
16+
int left = minDepth(root.left);
17+
int right = minDepth(root.right);
18+
19+
return (left == 0 || right == 0) ? 1 : Math.min(left, right) + 1;
20+
}
21+
}

‎src/main/java/com/chen/algorithm/study/test111/TreeNode.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.chen.algorithm.study.test111;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2019-11-01 00:03
6+
*/
7+
public class TreeNode {
8+
9+
int val;
10+
11+
TreeNode left;
12+
13+
TreeNode right;
14+
15+
public TreeNode() {
16+
}
17+
18+
public TreeNode(int val) {
19+
this.val = val;
20+
}
21+
22+
public int getVal() {
23+
return val;
24+
}
25+
26+
public void setVal(int val) {
27+
this.val = val;
28+
}
29+
30+
public TreeNode getLeft() {
31+
return left;
32+
}
33+
34+
public void setLeft(TreeNode left) {
35+
this.left = left;
36+
}
37+
38+
public TreeNode getRight() {
39+
return right;
40+
}
41+
42+
public void setRight(TreeNode right) {
43+
this.right = right;
44+
}
45+
}

‎src/main/java/com/chen/algorithm/study/test120/Solution.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package com.chen.algorithm.study.test120;
2+
3+
import java.util.List;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2020-05-17 20:07
8+
*/
9+
public class Solution {
10+
11+
public int minimumTotal(List<List<Integer>> triangle) {
12+
if (triangle == null || triangle.size() == 0) {
13+
return 0;
14+
}
15+
int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
16+
for (int i = triangle.size() - 1; i >= 0; i--) {
17+
List<Integer> rows = triangle.get(i);
18+
for (int j = 0; j < rows.size(); j++) {
19+
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + rows.get(j);
20+
}
21+
}
22+
return dp[0][0];
23+
}
24+
25+
}

‎src/main/java/com/chen/algorithm/study/test122/Solution.java

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package com.chen.algorithm.study.test122;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2020-05-16 23:36
6+
*/
7+
public class Solution {
8+
9+
10+
public static int maxProfit(int[] prices) {
11+
12+
int max = 0;
13+
14+
for (int i = 1; i < prices.length; i++) {
15+
if (prices[i] > prices[i - 1]) {
16+
max = max + (prices[i] - prices[i - 1]);
17+
}
18+
}
19+
return max;
20+
}
21+
22+
23+
public static void main(String[] args) {
24+
int[] n = {7, 1, 5, 3, 6, 4};
25+
System.out.println(maxProfit(n));
26+
27+
}
28+
29+
30+
}

‎src/main/java/com/chen/algorithm/study/test144/Solution.java

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package com.chen.algorithm.study.test144;
2+
3+
4+
import java.util.ArrayList;
5+
import java.util.List;
6+
import java.util.Stack;
7+
8+
/**
9+
* @author : chen weijie
10+
* @Date: 2020-05-11 23:21
11+
*/
12+
public class Solution {
13+
14+
public class TreeNode {
15+
int val;
16+
TreeNode left;
17+
TreeNode right;
18+
19+
TreeNode(int x) {
20+
val = x;
21+
}
22+
}
23+
24+
public List<Integer> preorderTraversal(TreeNode root) {
25+
26+
List<Integer> list = new ArrayList<>();
27+
Stack<TreeNode> stack = new Stack<>();
28+
stack.push(root);
29+
while (!stack.isEmpty()) {
30+
TreeNode temp = stack.pop();
31+
list.add(temp.val);
32+
33+
if (temp.right != null) {
34+
stack.push(temp.right);
35+
}
36+
if (temp.left != null) {
37+
stack.push(temp.left);
38+
}
39+
}
40+
return list;
41+
}
42+
43+
}

0 commit comments

Comments
 (0)