Lowest Common Ancestor of a Binary Tree

 It's recursive and expands the meaning of the function. If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is null/None/nil.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (right != null && left != null) {
            return root;
        } else {
            if (left == null) return right;
            else return left;
        }
    }
}

========

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        List<TreeNode> ans1 = new ArrayList<TreeNode>();
        findAncestors(root, p, ans1);
        List<TreeNode> ans2 = new ArrayList<TreeNode>();
        findAncestors(root, q, ans2);
        TreeNode res = null;
        for (int i = 0; i < ans1.size() && i < ans2.size(); i++) {
            if (ans1.get(i) == ans2.get(i))
                res = ans1.get(i);
            else
                break;
        }
        return res;
    }
   
    private boolean findAncestors(TreeNode root, TreeNode node, List<TreeNode> path) {
        if (root == null) {
            return false;
        }
        path.add(root);
        if (root == node) {
            return true;
        }
        if (findAncestors(root.left, node, path)) {
            return true;
        }
        if (findAncestors(root.right, node, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}