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