Problem

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

For the following binary tree:

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

Note

递归左右子树，若左右子树都有解，那么返回根节点；若仅左子树有解，返回左子树；若仅右子树有解，返回右子树；若都无解，返回null。

对于BST而言，更为简单：公共祖先一定是大于等于其中一个结点，小于等于另一个结点。那么若两个结点都小于当前的root结点，完全可以继续去比较第一个比root小的结点：root.left；若两个结点都大于当前的root结点，就去比较第一个比root大的结点：root.right；否则，一定是满足一个结点小于等于root，另一个结点大于等于root的情况了，返回root即可。

For the binary search tree, the root.val must be smaller than its right children but larger than its left children. Therefore, there are three basic possible relationships among root, p and q.

p.val >= root.val && q.val <= root.val;
p.val > root.val && q.val > root.val;
p.val < root.val && q.val < root.val;

Here we ignored the situation if we switch p and q, that's equivalent situation to the first one, of which the result is root. So we just need to dig into the 2nd and 3rd.
For the 2nd situation, replace root with root.right cause the common ancestor must be larger than root, then we can just use recursion to get the answer.
Same for the 3rd.

Solution

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null || root == A || root == B) return root;
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        if (left != null && right != null) return root;
        if (left != null && right == null) return left;
        if (left == null && right != null) return right;
        return null;
    }
}

For BST：

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}