1.题目描述：
设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。
注意：这不一定是二叉搜索树。
链接：https://leetcode-cn.com/problems/first-common-ancestor-lcci/
2.题解思路：
从根节点出发，考虑p、q的情况：
（1）如果p 、q中有一个是根节点，那么它本身就是首个共同祖先；
（2）如果p、q分别在根节点的左右子树中，那么它本身也是首个共同祖先；
（3）如果p、q都同在根节点的左子树或右子树中，那就用递归的方法，将左子节点或右子节点作为根节点求解。
3.代码实现：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//当root为空，就返回空
if (root == null) {
return null;
}
//当root是p或者q中的一个，满足(1)的条件，直接返回root
if (root == p || root == q) {
return root;
}
//在左子树中查找p和q
TreeNode left = lowestCommonAncestor(root.left, p, q);
//在右子树中查找p和q
TreeNode right = lowestCommonAncestor(root.right, p, q);
//如果left和right都不为空，说明p、q分别在左右子树上，满足(2)的条件，直接返回root
if (left != null && right != null) {
return root;
}
//如果左子树为空，说明p、q都在右子树中，将右子节点作为根节点，满足(3)
if (left == null) {
return right;
}
//如果右子树为空，说明p、q都在左子树中，将左子节点作为根节点，满足(3)
if (right == null) {
return left;
}
//如果左右子树都为空，说明p、q都不存在，本题不会出现这种情况
return null;
}
关于left和right，在递归过程中，要么值为null，要么就是我们找到的p或者q值。
当我们令 left = self.lowestCommonAncestor(root.left, p, q) 时，如果在左子树中找到了 p 或 q，left 会等于 p 或 q，同理，right 也是一样。
事实上，就是根据lowestCommonAncestor的返回值，来决定root往左子树还是右子树下移，直到最后某一个节点的left和right的值都不为空，那么它就是要求的首个共同祖先。
上边的代码可以进行简化：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//当root为空，就返回空，当root是p或者q中的一个，满足(1)的条件，直接返回root
if (root == null || root == p || root == q) {
return root;
}
//在左右子树中查找p和q
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return left != null ? right != null ? root : left : right;
}
复杂度分析：
- 时间复杂度：O(logn)，最优的情况是O(1)，最差的情况是O(logn)。
-
空间复杂度：O(1)，不需要额外开辟新的空间。
竟然击败了双百的人，纪念一下
