問(wèn)題描述

在一篇博客上看到了一個(gè)遞歸函數(shù)，但我感覺(jué)劃線的那一行似乎永遠(yuǎn)不為true呢？

因?yàn)楹瘮?shù)里的第一個(gè)判斷條件：

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

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

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

問(wèn)題解答

首先你要弄明白，這個(gè)遞歸函數(shù)的返回值有4種可能：

null，表示這次遞歸已經(jīng)碰到葉子節(jié)點(diǎn)，無(wú)法再繼續(xù)下去了。

p，表示這次遞歸已經(jīng)碰到p節(jié)點(diǎn)了。

q，表示這次遞歸已經(jīng)碰到q節(jié)點(diǎn)了。

lowestCommonAncestor，表示已經(jīng)找到的最低公共祖先節(jié)點(diǎn)。

為何這樣說(shuō)，前3種可能，你應(yīng)該很好理解，因?yàn)閺?lt;1> if (!root || p == root || q == root) return root;這行代碼可以看出來(lái)。

那么再看（我就簡(jiǎn)寫(xiě)了）<2> left = lowestCommonAncestor(left, p, q);<3> right = lowestCommonAncestor(right, p, q);這兩行。在真正的lowestCommonAncestor被找到之前，這個(gè)函數(shù)只可能會(huì)返回null，q，p。再看這兩行判斷<4> if (left && left != p && left != q) return left;<5> if (right && right != p && right != q) return right;當(dāng)<2>，<3>兩處的返回值是null，p，q的時(shí)候，這兩處判斷的條件都無(wú)法滿足，所以不會(huì)返回。所以要進(jìn)入再下面的判斷<6> if (left && right) return root;這句什么意思？如果從<4>，<5>的判斷處沒(méi)有返回，說(shuō)明left和right只能是null，p，q中的一個(gè)，而這里了又限定了left和right必須是非null，意思就是這時(shí)候left和right必定一個(gè)是p，一個(gè)是q。那么這個(gè)時(shí)候，本層遞歸函數(shù)的root（注意是本層遞歸函數(shù)）就是那個(gè)lowestCommonAncesstor，于是就返回它。最后一句<7> return left ? left : right;既然到了這里，就說(shuō)明left和right里面至少有一個(gè)是null，那么就返回非null的那個(gè)，或者如果兩個(gè)都是null就返回null。

現(xiàn)在倒回去再看一下lowestCommonAncesstor這個(gè)遞歸函數(shù)在<2>，<3>兩處的調(diào)用，你可以把它看成是去當(dāng)前節(jié)點(diǎn)的left和right中分別去尋找p，和q，那么無(wú)非結(jié)果有4種：

返回null，說(shuō)明p，q根本不在這個(gè)分支中。

返回p，說(shuō)明這個(gè)分支中只有p，沒(méi)有q。

返回q，說(shuō)明這個(gè)分支中只有q，沒(méi)有p。

返回lowestCommonAncesstor，說(shuō)明這個(gè)分支中既有p又有q，于是就已經(jīng)找到他們的公共祖先啦！

可能說(shuō)的還是不夠透徹，希望對(duì)你有幫助：）

第一個(gè)條件是判斷root，第二個(gè)是判斷l(xiāng)eft，有什么聯(lián)系嗎？