https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/ https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/ http://www.lintcode.com/en/problem/lowest-common-ancestor/

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

解题：分治法经典题目，要求寻找最近公共祖先，终止条件为到达null node或找到其中一个tree node。所以在每一层返回的时候我们需要检测左右是否为空，如果左右都不为空我们就返回当前node。

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null || root == A || root == B) {
            return root;
        }

        // Divide
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);

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