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
| class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
var path1 = search(root, p.val);
var path2 = search(root, q.val);
for (int i = path1.size() - 1; i >= 0; i--) {
var ans = path1.get(i);
if (path2.contains(ans)) {
return ans;
}
}
return null;
}
private List<TreeNode> search(TreeNode root, int target) {
List<TreeNode> path = new ArrayList<>();
if (root == null) {
return path;
}
while (root.val != target) {
path.add(root);
if (root.val > target) {
root = root.left;
} else {
root = root.right;
}
}
path.add(root);
return path;
}
}
|
