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

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).”

     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      4       7       9
      /  \
     3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

思路就是找到一个节点的所有父节点，放在一个队列里面。然后两个节点的所有父节点形成的两个队列找到分叉（最后一个相同的节点），就是最近的一个父节点。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        TreeNode t = null;
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        seekNode(root, p, q1);
        seekNode(root, q, q2);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            if (q1.peek().val == q2.peek().val) {
                t = q1.poll();
                q2.poll();
            } else
                return t;
        }
        return p;
    }

    public void seekNode(TreeNode root, TreeNode t,
            Queue<TreeNode> queue) {
        queue.offer(root);
        if (t.val < root.val)
            seekNode(root.left, t, queue);
        if (t.val > root.val)
            seekNode(root.right, t, queue);
    }

递归实现

    // 在root为根的二叉树中找A,B的LCA:
    // 如果找到了就返回这个LCA
    // 如果只碰到A，就返回A
    // 如果只碰到B，就返回B
    // 如果都没有，就返回null
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
        if (root == null || root == node1 || root == node2) {
            return root;
        }

        // Divide
        TreeNode left = lowestCommonAncestor(root.left, node1, node2);
        TreeNode right = lowestCommonAncestor(root.right, node1, node2);

        // Conquer
        if (left != null && right != null) {
            return root;
        } 
        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        return null;
    }