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