最近公共祖先 LCA

http://www.lintcode.com/en/problem/lowest-common-ancestor/

注意点：结果的结构肯定是下面：  所以左右子树仅有三种返回结果，null，A,B。 （所以其实题目中A,B一定都是在树中的，不可能出现其中一个不再树中的情况，

　　　　　　　　　　　　　　所以代码最后返回null的情况是不可能出现的。）

　　　　　　　　　　　　　　　　左右都非null，那肯定一个是A, 一个B，所以当前结点为LCA；

　　　　　　　　　　　　　　　　在前一个判断的基础上，左非null，则右一定是null，说明A，B两个结点至少一个在左子上，左子是至少一个结点的祖先

　　　　　　　　　　　　　　　　（如果当前结点是root，那左子非null，右子null，因为A，B一定都在树中，那左子一定是AB的公共祖先。）

　　　　　　　　　　　  *

　　　　　　　　　　A

　　　　　　　　1　　　　 2

　　　　　　3　　4       B

 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) return left;
     if(right != null) return right;
     return null;       //分治，左右子树只可能有三种结果，A,B或者null
                        // 左右子树都返回null，说明查找的结果不存在；左非null(则左只可能是A或B)，右null，说明A,B都在左子树上。         
}