這題比235題少了個條件，不是搜索樹BST了，是普通二叉樹。就不能用BST性質(zhì)做了。還是用遞歸，但是思維難度大了。

遞歸尋找左右子樹的LCA，如果左右子樹的LCA不為空，那么LCA就是root；如果其中一個節(jié)點為空，那么LCA就是另一個節(jié)點。
這題我們考慮初始條件，如果只有一層，比如是一棵這樣的樹：
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結(jié)果可以看出來就是null或者p或者q啊。
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    //在左子樹，右子樹都找到了p，q，說明這個root就是我們要找的node，p, q分別在root兩側(cè)
    if (left != null && right != null) {
        return root;
    }
    return left == null ? right : left;

}

網(wǎng)上看到一個人做了優(yōu)化：

在找完左子樹的共同父節(jié)點時如果結(jié)果存在，且不是p或q，那么不用再找右子樹了，直接返回這個結(jié)果即可

注意這題的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;這句話好像永遠不會執(zhí)行到的樣子啊。。
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/

http://www.cnblogs.com/springfor/p/4141924.html