/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> search(TreeNode root, TreeNode node) {
        if(root == null) return null;

        if(root == node) {
            List<Integer> path = new ArrayList<>();
            path.add(root.val);
            return path;
        }

        List<Integer> left = search(root.left, node);
        if(left != null) {
            left.add(root.val);
            return left;
        }
        List<Integer> right = search(root.right, node);
        if(right != null) {
            right.add(root.val);
            return right;
        }

        return null;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<Integer> pathp = search(root, p);
        List<Integer> pathq = search(root, q);

        int i = pathp.size()-1, j = pathq.size()-1;

        while(i >= 0 && j >= 0) {
            if(pathp.get(i) == pathq.get(j)) {
                i--; j--;
            }else{
                break;
            }
        }

        // System.out.println(pathp.get(i+1));

        return new TreeNode(pathp.get(i+1));
    }
}