这题比235题少了个条件，不是搜索树BST了，是普通二叉树。就不能用BST性质做了。还是用递归，但是思维难度大了。
递归寻找左右子树的LCA，如果左右子树的LCA不为空，那么LCA就是root；如果其中一个节点为空，那么LCA就是另一个节点。
这题我们考虑初始条件，如果只有一层，比如是一棵这样的树：
1
/
23
那么就容易想了。千万别往递归深处想，会绕进去的。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//如果root就是p , q中的一个，return root
if (null == root || root == p || root == q) return root;
//在左右子树分别寻找p,q，我疑惑的是这个left，right分别是什么呢？从上面的return结果可以看出来就是null或者p或者q啊。
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
//在左子树，右子树都找到了p，q，说明这个root就是我们要找的node，p, q分别在root两侧
if (left != null && right != null) {
return root;
}
return left == null ? right : left;
}
网上看到一个人做了优化：
在找完左子树的共同父节点时如果结果存在，且不是p或q，那么不用再找右子树了，直接返回这个结果即可
注意这题的if条件是判断root==p而不是p.val。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
if (left != null && left != q && left != p) return left;
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (right != null && right != q && right != p) return right;
if (left != null && right != null) return root;
else return left != null ? left : right;
}
但我觉得他那个 if (left != null && left != q && left != p) return left;这句话好像永远不会执行到的样子啊。。
https://segmentfault.com/q/1010000008922088?_ea=1776493
对于递归，我是不是有一天会开窍呢。。
reference：
https://discuss.leetcode.com/topic/18561/4-lines-c-java-python-ruby
http://bookshadow.com/weblog/2015/07/13/leetcode-lowest-common-ancestor-binary-tree/
