-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_236.java
More file actions
46 lines (40 loc) · 1.12 KB
/
Copy pathP_236.java
File metadata and controls
46 lines (40 loc) · 1.12 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
package leetcode.medium;
import utils.DataStructures.TreeNode;
@SuppressWarnings("ConstantConditions")
public class P_236 {
private static class Pair {
int mask;
TreeNode lca;
Pair(int mask, TreeNode lca) {
this.mask = mask;
this.lca = lca;
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return dfs(root, p, q).lca;
}
private static Pair dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return new Pair(0, null);
}
final Pair l = dfs(root.left, p, q);
final Pair r = dfs(root.right, p, q);
TreeNode lca = null;
int mask;
if (l.lca != null) {
lca = l.lca;
mask = 3;
} else if (r.lca != null) {
lca = r.lca;
mask = 3;
} else {
mask = l.mask | r.mask;
if (root == p) { mask |= 1; }
if (root == q) { mask |= 2; }
if (mask == 3) {
lca = root;
}
}
return new Pair(mask, lca);
}
}