Lowest Common Ancestor of a Binary Tree LeetCode solution in Java

1
/**
2
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode
3
 * right; TreeNode(int x) { val = x; } }
4
 */
5
class Solution {
6
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
7
    List<TreeNode> path_to_p = new ArrayList<>();
8
    List<TreeNode> path_to_q = new ArrayList<>();
9
    getPath(root, p, path_to_p);
10
    getPath(root, q, path_to_q);
11
    int n = path_to_q.size() > path_to_p.size() ? path_to_p.size() : path_to_q.size();
12
    TreeNode anscesstor = root;
13
    for (int i = 0; i < n; i++) {
14
      if (path_to_q.get(i) == path_to_p.get(i)) anscesstor = path_to_p.get(i);
15
    }
16
    return anscesstor;
17
  }
18

19
  boolean getPath(TreeNode root, TreeNode target, List<TreeNode> list) {
20
    if (root == null) return false;
21
    list.add(root);
22
    if (root == target) return true;
23
    if (getPath(root.left, target, list) || getPath(root.right, target, list)) {
24
      return true;
25
    }
26
    list.remove(list.size() - 1);
27
    return false;
28
  }
29
}