Skip to content

Commit 0081b58

Browse files
617076674617076674
committed
2020-4-20
1 parent 2cd340d commit 0081b58

File tree

13 files changed

+159
-26
lines changed

13 files changed

+159
-26
lines changed

‎lcci0408_first_common_ancestor/Solution.java

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package lcci0408_first_common_ancestor;
2+
3+
public class Solution {
4+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
5+
if (null == root || p == root || q == root) {
6+
return root;
7+
}
8+
TreeNode leftResult = lowestCommonAncestor(root.left, p, q),
9+
rightResult = lowestCommonAncestor(root.right, p, q);
10+
if (null == leftResult) {
11+
return rightResult;
12+
}
13+
if (null == rightResult) {
14+
return leftResult;
15+
}
16+
return root;
17+
}
18+
}

‎lcci0408_first_common_ancestor/TreeNode.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package lcci0408_first_common_ancestor;
2+
3+
public class TreeNode {
4+
int val;
5+
6+
TreeNode left;
7+
8+
TreeNode right;
9+
10+
TreeNode(int x) {
11+
val = x;
12+
}
13+
}

‎lcci0409_bst_sequences/Solution.java

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package lcci0409_bst_sequences;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* 左右孩子由root.val来区分，因此只需要保证左孩子节点的相对顺序和右孩子节点的相对顺序即可，左右孩子节点的顺序可以交错。
8+
*
9+
* 执行用时：6ms，击败71.08%。消耗内存：41.1MB，击败100.00%。
10+
*/
11+
public class Solution {
12+
private List<List<Integer>> result = new ArrayList<>();
13+
14+
public List<List<Integer>> BSTSequences(TreeNode root) {
15+
if (null == root) {
16+
result.add(new ArrayList<>());
17+
return result;
18+
}
19+
List<List<Integer>> leftResult = BSTSequences(root.left), rightResult = BSTSequences(root.right);
20+
for (List<Integer> leftList : leftResult) {
21+
for (List<Integer> rightList : rightResult) {
22+
List<Integer> list = new ArrayList<>();
23+
list.add(root.val);
24+
merge(leftList, rightList, 0, 0, list);
25+
}
26+
}
27+
return result;
28+
}
29+
30+
private void merge(List<Integer> leftList, List<Integer> rightList, int index1, int index2, List<Integer> list) {
31+
if (index1 == leftList.size() && index2 == rightList.size()) {
32+
result.add(new ArrayList<>(list));
33+
return;
34+
}
35+
if (index1 == leftList.size()) {
36+
List<Integer> tmp = new ArrayList<>(list);
37+
for (int i = index2; i < rightList.size(); i++) {
38+
tmp.add(rightList.get(i));
39+
}
40+
result.add(tmp);
41+
} else if (index2 == rightList.size()) {
42+
List<Integer> tmp = new ArrayList<>(list);
43+
for (int i = index1; i < leftList.size(); i++) {
44+
tmp.add(leftList.get(i));
45+
}
46+
result.add(tmp);
47+
} else {
48+
list.add(leftList.get(index1));
49+
merge(leftList, rightList, index1 + 1, index2, list);
50+
list.remove(list.size() - 1);
51+
list.add(rightList.get(index2));
52+
merge(leftList, rightList, index1, index2 + 1, list);
53+
list.remove(list.size() - 1);
54+
}
55+
}
56+
}

‎question0236/TreeNode.java renamed to ‎lcci0409_bst_sequences/TreeNode.java

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,13 @@
1-
package question0236;
1+
package lcci0409_bst_sequences;
22

33
public class TreeNode {
44
int val;
5+
56
TreeNode left;
7+
68
TreeNode right;
79

810
TreeNode(int x) {
911
val = x;
1012
}
11-
}
13+
}

‎lcci0410_check_subtree/Solution.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package lcci0410_check_subtree;
2+
3+
/**
4+
* 执行用时：1ms，击败97.13%。消耗内存：42.1MB，击败100.00%。
5+
*/
6+
public class Solution {
7+
public boolean checkSubTree(TreeNode t1, TreeNode t2) {
8+
if (null == t1 && null != t2) {
9+
return false;
10+
}
11+
if (isSameTree(t1, t2)) {
12+
return true;
13+
}
14+
if (checkSubTree(t1.left, t2)) {
15+
return true;
16+
}
17+
if (checkSubTree(t1.right, t2)) {
18+
return true;
19+
}
20+
return false;
21+
}
22+
23+
private boolean isSameTree(TreeNode t1, TreeNode t2) {
24+
if (null == t1 || t2 == null) {
25+
return t1 == null && t2 == null;
26+
}
27+
if (t1.val != t2.val) {
28+
return false;
29+
}
30+
return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
31+
}
32+
}

‎question0572/TreeNode.java renamed to ‎lcci0410_check_subtree/TreeNode.java

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,13 @@
1-
package question0572;
1+
package lcci0410_check_subtree;
22

33
public class TreeNode {
44
int val;
5+
56
TreeNode left;
7+
68
TreeNode right;
9+
710
TreeNode(int x) {
811
val = x;
912
}
10-
}
13+
}

‎question0200_number_of_islands/Solution1.java

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,6 @@
11
package question0200_number_of_islands;
22

33
/**
4-
* https://leetcode-cn.com/problems/number-of-islands/
5-
*
64
* 图的深度优先遍历求连通分量。
75
*
86
* 时间复杂度和空间复杂度均是O(m * n)，其中m为grid数组的行数，n是grid数组的列数。

‎question0200_number_of_islands/Solution2.java

Lines changed: 3 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -4,27 +4,24 @@
44
import java.util.Queue;
55

66
/**
7-
* https://leetcode-cn.com/problems/number-of-islands/
8-
*
97
* 图的广度优先遍历求连通分量。
108
*
119
* 时间复杂度是O(m * n)，其中m为grid数组的行数，n是grid数组的列数。空间复杂度是O(min(m, n))。
1210
*
1311
* 执行用时：6ms，击败27.13%。消耗内存：41.2MB，击败84.22%。
1412
*/
1513
public class Solution2 {
16-
private int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
17-
18-
private int m, n;
19-
2014
public int numIslands(char[][] grid) {
15+
int m;
2116
if (null == grid || (m = grid.length) == 0) {
2217
return 0;
2318
}
19+
int n;
2420
if (null == grid[0] || (n = grid[0].length) == 0) {
2521
return 0;
2622
}
2723
int count = 0;
24+
int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
2825
for (int i = 0; i < m; i++) {
2926
for (int j = 0; j < n; j++) {
3027
if (grid[i][j] == '1') {

‎question0200_number_of_islands/Solution3.java

Lines changed: 4 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -4,8 +4,6 @@
44
import java.util.Set;
55

66
/**
7-
* https://leetcode-cn.com/problems/number-of-islands/
8-
*
97
* 并查集实现。
108
*
119
* 如何将一个二维数组映射成一个一维数组呢？
@@ -19,14 +17,12 @@
1917
public class Solution3 {
2018
private int[] parent; //并查集数组
2119

22-
private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
23-
24-
private int m, n;
25-
2620
public int numIslands(char[][] grid) {
21+
int m;
2722
if (null == grid || (m = grid.length) == 0) {
2823
return 0;
2924
}
25+
int n;
3026
if (null == grid[0] || (n = grid[0].length) == 0) {
3127
return 0;
3228
}
@@ -42,6 +38,7 @@ public int numIslands(char[][] grid) {
4238
}
4339
}
4440
}
41+
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
4542
for (int i = 0; i < m; i++) {
4643
for (int j = 0; j < n; j++) {
4744
if (grid[i][j] == '1') {
@@ -70,8 +67,7 @@ private int findFather(int x) {
7067
while (x != parent[x]) {
7168
x = parent[x];
7269
}
73-
//路径压缩
74-
while (a != parent[a]) {
70+
while (a != parent[a]) { //路径压缩
7571
int z = a;
7672
a = parent[a];
7773
parent[z] = x;

‎question0236/Solution.java renamed to ‎question0236_lowest_common_ancestor_of_a_binary_tree/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package question0236;
1+
package question0236_lowest_common_ancestor_of_a_binary_tree;
22

33
/**
44
* 递归。

‎question0236_lowest_common_ancestor_of_a_binary_tree/TreeNode.java

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package question0236_lowest_common_ancestor_of_a_binary_tree;
2+
3+
public class TreeNode {
4+
int val;
5+
TreeNode left;
6+
TreeNode right;
7+
8+
TreeNode(int x) {
9+
val = x;
10+
}
11+
}

‎question0572/Solution.java renamed to ‎question0572_subtree_of_another_tree/Solution.java

Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,6 @@
1-
package question0572;
1+
package question0572_subtree_of_another_tree;
22

33
/**
4-
* @author qianyihui
5-
* @date 2019-06-27
6-
*
74
* 递归实现。
85
*
96
* 时间复杂度是O(mn)，其中m为s中的节点个数，n为t中的节点个数。
@@ -44,4 +41,4 @@ public boolean isSame(TreeNode node1, TreeNode node2) {
4441
}
4542
return isSame(node1.left, node2.left) && isSame(node1.right, node2.right);
4643
}
47-
}
44+
}

‎question0572_subtree_of_another_tree/TreeNode.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package question0572_subtree_of_another_tree;
2+
3+
public class TreeNode {
4+
int val;
5+
TreeNode left;
6+
TreeNode right;
7+
TreeNode(int x) {
8+
val = x;
9+
}
10+
}

0 commit comments

Comments
 (0)