在一篇博客上看到了一個遞歸函數，但我感覺劃線的那一行似乎永遠不為true呢？
因為函數裏的第一個判斷條件：
if (!root || p == root || q == root) return root;就決定了left必定是p,q,null之一吧？
我對遞歸的理解不太深刻,不知道理解的對不對？謝謝。
迷茫2017-04-18 10:55:18
首先你要弄清楚，這個遞歸函數的回傳值有4種可能：
null，表示這次遞歸已經碰到葉子節點，無法再繼續下去了。
p，表示這次遞歸已經碰到p節點了。
q，表示這次遞歸已經碰到q節點了。
lowestCommonAncestor，表示已找到的最低公共祖先節點。
為何這樣說，前3種可能，你應該很好理解，因為從
<1> if (!root || p == root || q == root) return root;
這行程式碼可以看出來。
那麼再看（我就簡寫了）
<2> left = lowestCommonAncestor(left, p, q);
<3> right = lowestCommonAncestor(right, p, q);
這兩行。在真正的lowestCommonAncestor被找到之前，這個函數只可能會回傳null，q，p。
再看這兩行判斷
<4> if (left && left != p && left != q) return left;
<5> if (right && right != p && right != q) return right;
當<2>，<3>兩處的回傳值是null，p，q的時候，這兩處判斷的條件都無法滿足，所以不會回傳。
所以要進入再下面的判斷
<6> if (left && right) return root;
這句話什麼意思？如果從<4>，<5>的判斷處沒有返回，表示left和right只能是null，p，q中的一個，
而這裡了又限定了left和right必須是非null，意思就是這時候left而right必定一個是p，一個是q。
那麼這個時候，本層遞歸函數的root（注意是本層遞歸函數）就是那個lowestCommonAncesstor，
於是就回傳它。
最後一句
<7> return left ? left : right;
既然到了這裡，就說明left和right裡面至少有一個是null，那麼就返回非null的那個，或者如果兩個
都是null就返回null 。
現在倒回去再看一下lowestCommonAncesstor這個遞歸函數在<2>，<3>兩處的調用，你可以把它看成是去當前
節點的left和right中分別去尋找p，和q，那麼無非結果有4種：
回傳null，說明p，q根本不在這個分支。
回傳p，表示這個分支中只有p，沒有q。
回傳q，表示這個分支中只有q，沒有p。
返回lowestCommonAncesstor，說明這個分支中既有p又有q，於是就已經找到他們的公共祖先啦！
可能說的還是不夠透徹，希望對你有幫助：）
