236. Lowest Common Ancestor of a Binary Tree (Medium)

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes5and1is3. Another example is LCA of nodes5and4is5, since a node can be a descendant of itself according to the LCA definition.

Solution 1: Recursive, DFS O(n); O(h)

    /**
     * Recursive O(n); O(h)
     * Recurrence relation:
     * Search for p and q in left and right subtrees.
     * If both are found, it means the two nodes are in different subtrees, root should be their LCA.
     * If one of them is null, it means no possible LCA found for p or q.
     * Then the one that is not null should be their LCA.
     * Base case:
     * If root is null, return null; if root is p or q, return p or q, respectively.
     */

    /**
     * 从上向下搜索, 遇到p或q或null, return之
     * 回溯过程中,
     * (1).左return != null且右return != null (即左p右q或左q右p), 说明current root是LCA, return之;
     * (2).左右谁不为null就向上return谁 (即p或q, 或null).
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root; //tricky
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        return left == null ? right : right == null ? left : root;
    }

Solution 2: Iterative, BFS O(n); O(n)

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        parent.put(root, null);
        queue.add(root);
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = queue.poll();
            if (node != null) {
                parent.put(node.left, node);
                parent.put(node.right, node);
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        Set<TreeNode> set = new HashSet<>();
        while (p != null) {
            set.add(p);
            p = parent.get(p);
        }
        while (!set.contains(q)) {
            q = parent.get(q);
        }
        return q;
    }

Follow Up:

1.Given a tree, find the smallest subtree that contains all of the tree's deepest nodes. http://www.1point3acres.com/bbs/thread-167887-1-1.html