8000 refactor 235 · arnav1996/Leetcode-1@e929509 · GitHub
[go: up one dir, main page]
Skip to content

Commit e929509

Browse files
fishercoder1534fishercoder1534
committed
refactor 235
1 parent 92f32d6 commit e929509

File tree

2 files changed

+78
-6
lines changed

2 files changed

+78
-6
lines changed

‎src/main/java/com/fishercoder/solutions/_235.java

Lines changed: 24 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -10,12 +10,12 @@
1010
* “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants
1111
* (where we allow a node to be a descendant of itself).”
1212
13-
_______6______
14-
/ \
15-
___2__ ___8__
16-
/ \ / \
17-
0 _4 7 9
18-
/ \
13+
_______6______
14+
/ \
15+
___2__ ___8__
16+
/ \ / \
17+
0 4 7 9
18+
/ \
1919
3 5
2020
2121
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6.
@@ -38,4 +38,22 @@ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
3838
return root;
3939
}
4040
}
41+
42+
public static class Solution2 {
43+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
44+
if (p == root || q == root || p == q) {
45+
return root;
46+
}
47+
if (p.val < root.val && q.val > root.val) {
48+
return root;
49+
}
50+
if (p.val < root.val && q.val < root.val) {
51+
return lowestCommonAncestor(root.left, p, q);
52+
}
53+
if (p.val > root.val && q.val > root.val) {
54+
return lowestCommonAncestor(root.right, p, q);
55+
}
56+
return root;
57+
}
58+
}
4159
}

‎src/test/java/com/fishercoder/_235Test.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import com.fishercoder.solutions._235;
6+
import java.util.Arrays;
7+
import org.junit.BeforeClass;
8+
import org.junit.Test;
9+
10+
import static org.junit.Assert.assertEquals;
11+
12+
public class _235Test {
13+
private static _235.Solution1 solution1;
14+
private static _235.Solution2 solution2;
15+
private static TreeNode root;
16+
private static TreeNode p;
17+
private static TreeNode q;
18+
19+
@BeforeClass
20+
public static void setup() {
21+
solution1 = new _235.Solution1();
22+
solution2 = new _235.Solution2();
23+
}
24+
25+
@Test
26+
public void test1() {
27+
root = TreeUtils.constructBinaryTree(Arrays.asList(6, 2, 8, 0, 4, 7, 9, 3, 5));
28+
TreeUtils.printBinaryTree(root);
29+
30+
p = TreeUtils.constructBinaryTree(Arrays.asList(2, 0, 4, 3, 5));
31+
TreeUtils.printBinaryTree(p);
32+
33+
q = TreeUtils.constructBinaryTree(Arrays.asList(8, 7, 9));
34+
TreeUtils.printBinaryTree(q);
35+
36+
assertEquals(root, solution1.lowestCommonAncestor(root, p, q));
37+
assertEquals(root, solution2.lowestCommonAncestor(root, p, q));
38+
}
39+
40+
@Test
41+
public void test2() {
42+
root = TreeUtils.constructBinaryTree(Arrays.asList(6, 2, 8, 0, 4, 7, 9, 3, 5));
43+
TreeUtils.printBinaryTree(root);
44+
45+
p = TreeUtils.constructBinaryTree(Arrays.asList(2, 0, 4, 3, 5));
46+
TreeUtils.printBinaryTree(p);
47+
48+
q = TreeUtils.constructBinaryTree(Arrays.asList(4));
49+
TreeUtils.printBinaryTree(q);
50+
51+
assertEquals(p, solution1.lowestCommonAncestor(root, p, q));
52+
assertEquals(p, solution2.lowestCommonAncestor(root, p, q));
53+
}
54+
}

0 commit comments

Comments
 (0)
0