java - 一段遞歸代碼的問題

問題描述

在一篇博客上看到了一個遞歸函數，但我感覺劃線的那一行似乎永遠不為true呢？

因為函數里的第一個判斷條件：

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

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

我對遞歸的理解不太深刻,不知道理解的對不對？謝謝。

問題解答

首先你要弄明白，這個遞歸函數的返回值有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，于是就已經找到他們的公共祖先啦！

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

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