java - 一段递归代码的问题

Question

在一篇博客上看到了一个递归函数，但我感觉划线的那一行似乎永远不为true呢？

因为函数里的第一个判断条件：

if (!root || p == root || q == root) return root;

就决定了left必定是p,q,null之一吧？

我对递归的理解不太深刻,不知道理解的对不对？谢谢。

Answer 1

首先你要弄清楚，這個遞歸函數的回傳值有4種可能：

1. null，表示這次遞歸已經碰到葉子節點，無法再繼續下去了。

2. p，表示這次遞歸已經碰到p節點了。

3. q，表示這次遞歸已經碰到q節點了。

4. 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種：

1. 回傳null，說明p，q根本不在這個分支。

2. 回傳p，表示這個分支中只有p，沒有q。

3. 回傳q，表示這個分支中只有q，沒有p。

4. 返回lowestCommonAncesstor，說明這個分支中既有p又有q，於是就已經找到他們的公共祖先啦！

可能說的還是不夠透徹，希望對你有幫助：）

Answer 2

第一個條件是判斷root，第二個是判斷left，有什麼關聯嗎？