首先是最近公共祖先的概念(什么是最近公共祖先？)：
在一棵沒(méi)有環(huán)的樹(shù)上，每個(gè)節(jié)點(diǎn)肯定有其父親節(jié)點(diǎn)和祖先節(jié)點(diǎn)，而最近公共祖先，就是兩個(gè)節(jié)點(diǎn)在這棵樹(shù)上深度最大的公共的祖先節(jié)點(diǎn)。
換句話(huà)說(shuō)，就是兩個(gè)點(diǎn)在這棵樹(shù)上距離最近的公共祖先節(jié)點(diǎn)。
所以L(fǎng)CA主要是用來(lái)處理當(dāng)兩個(gè)點(diǎn)僅有唯一一條確定的最短路徑時(shí)的路徑。
有人可能會(huì)問(wèn)：那他本身或者其父親節(jié)點(diǎn)是否可以作為祖先節(jié)點(diǎn)呢？
答案是肯定的，很簡(jiǎn)單，按照人的親戚觀念來(lái)說(shuō)，你的父親也是你的祖先，而LCA還可以將自己視為祖先節(jié)點(diǎn)。
舉個(gè)例子吧，如下圖所示４和５的最近公共祖先是２，５和３的最近公共祖先是１
網(wǎng)友評(píng)論
