题解 | #二分查找-II#
在二叉树中找到两个节点的最近公共祖先
http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
本题重点是深度遍历
通过返回空状态把叶子向上浮动
向上浮动的叶子找到第一个交点后再继续浮动到跟节点，最后返回的就是交点
public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
// write code here
return DFS(root,o1,o2).val;
}
//重点是把空和要求的叶子向上移动
public TreeNode DFS(TreeNode root, int o1, int o2) {
if (root == null) return root;//空情况直接返回
if(root.val == o1 || root.val == o2) return root;//找到要的叶子了
//后序遍历
TreeNode left = DFS(root.left, o1, o2);
TreeNode right = DFS(root.right, o1, o2);
//只能返回包含两个要求叶子的支树，不包含叶子就把null向上传递
if(left==null&&right==null)return null;
else if(left!=null&&right!=null)return root;
//当开始向上单独传递左或者右的时候，实际上是向上移动叶子
else if(left == null)return right;
else return left;
} 
