大家好，今天我們要討論的主題是，二叉樹中兩節(jié)點的最近公共祖先。

題目選自LeetCode 236，具體如下。已知二叉樹的根節(jié)點指針root，樹上的兩個不同節(jié)點的指針p和q，求p、q兩個節(jié)點的最近公共祖先。

例如，如果root、p和q分別指向3、6、4，那么就應(yīng)該返回節(jié)點5的地址。

我們可以再多舉幾個例子。例如，p和q指向1和2，則應(yīng)該返回3的地址，如果指向5和4，則返回5本身的地址。

問題分析

為了求出樹上任意兩個節(jié)點的最近公共祖先，需要先明確如下3個問題。

1，如何求某節(jié)點的祖先節(jié)點?

2，如何求兩節(jié)點的公共祖先?

3，如何求所有公共祖先中最近的那個節(jié)點?

關(guān)于問題1，求某節(jié)點的祖先節(jié)點，就是求根節(jié)點到該節(jié)點，路徑上的所有節(jié)點。例如，求q的祖先節(jié)點，就需要找到3、5、2、4這些節(jié)點的地址。

關(guān)于問題2，求兩個節(jié)點的公共祖先，就是求，同時出現(xiàn)在，兩個節(jié)點路徑上的節(jié)點。例如，根節(jié)點到p的路徑上有3、5、6，到q的路徑上有3、5、2、4，兩條路徑上同時出現(xiàn)了3與5，所以它們是p與q的公共祖先。

關(guān)于問題3，求最近的公共祖先，就是求，同時出現(xiàn)在兩條路徑上，離根最遠、離兩節(jié)點最近的節(jié)點。例如，p和q的公共祖先是3和5，5距離根節(jié)點最遠，距離p、q最近，所以5就是p和q的最近公共祖先。

算法設(shè)計

因此總結(jié)題目的算法設(shè)計如下，其中包括2個步驟。

1.求出p和q兩節(jié)點的路徑。

2.求出兩條路徑上最后一個地址相同的節(jié)點，即為最近的公共祖先。

對于步驟1，求某節(jié)點的路徑，就是要保存根節(jié)點到該節(jié)點之間，所有節(jié)點的指針。在這個過程中，需要設(shè)置一個棧，來存儲路徑上的節(jié)點指針。

這里需要特別說明，棧中保存的是節(jié)點的地址，而不是節(jié)點中的數(shù)據(jù)。我們?yōu)榱朔奖阏f明算法，才使用數(shù)據(jù)來表示某個節(jié)點。實際上，棧中應(yīng)該保存，是這樣的16進制地址。

當(dāng)找到該節(jié)點時，從棧底到棧頂存儲的節(jié)點即為從根節(jié)點到該節(jié)點的路徑。例如，q的路徑是3、5、2、4。在找到q時，從棧底到棧頂就會存儲3、5、2、4這四個節(jié)點的指針。

在搜索路徑時，需要使用二叉樹的深度優(yōu)先搜索算法。從根節(jié)點開始遍歷，直到找到待搜索的節(jié)點。例如，搜索q節(jié)點，從根節(jié)點3開始，依次遍歷3、5、6、2、7、4，最終找到節(jié)點q。

具體來說，在前序遍歷到某一節(jié)點時，節(jié)點的地址入棧。例如，當(dāng)遍歷到節(jié)點6時，節(jié)點3、5、6按照順序存儲至棧中。

當(dāng)某節(jié)點完成遍歷后，需要將該節(jié)點的地址從棧中彈出。例如，當(dāng)節(jié)點6完成遍歷后，需要將6從棧中彈出。

接著搜索會回溯到節(jié)點5，而棧中剛好存儲了從根節(jié)點到節(jié)點5路徑上的節(jié)點。因此，上述算法就保證了，棧會一直存儲，根節(jié)點到當(dāng)前正在遍歷節(jié)點的路徑。

搜索q節(jié)點的詳細過程

搜索q節(jié)點路徑的具體過程如下。

首先訪問根節(jié)點3，3入棧。然后是5和6，入棧。6是葉節(jié)點，訪問結(jié)束后，將6從棧中彈出。

這樣，5的左子樹就完成了搜索，然后要繼續(xù)搜索5的右子樹。

接著節(jié)點2入棧，然后是7。7是葉節(jié)點，入棧后即出棧。節(jié)點2的左子樹完成搜索后，訪問2的右子樹，節(jié)點4。

這時就找到了目標節(jié)點q，搜索結(jié)束。此時從棧低到棧頂存儲的3、5、2、4，即為根節(jié)點至q節(jié)點的路徑。

求最近的公共祖先

得到p和q的路徑后，在兩條路徑上尋找離根節(jié)點最遠的公共節(jié)點。這個過程需要使用指針，同時遍歷p和q的路徑，最后一個相同的節(jié)點即為最近公共祖先。

例如， p的路徑是3、5、6，q的路徑是3、5、2、4 ，同時出現(xiàn)兩條路徑上的節(jié)點是3和5。最后一個相同節(jié)點是5，所以5是最近的公共祖先。

代碼實現(xiàn)

定義函數(shù)dfs，求指定節(jié)點的路徑。函數(shù)有4個參數(shù)， node指向當(dāng)前正在搜索的節(jié)點，search指向待查找的節(jié)點，stack是存儲節(jié)點路徑的棧， path存儲search節(jié)點的路徑。

在函數(shù)中，如果當(dāng)前訪問的node指向空，搜索結(jié)束，直接返回。否則將node壓入棧中。

如果node和search相等，則說明找到了目標節(jié)點，stack中就存儲了結(jié)果路徑，將path賦值為stack，函數(shù)返回。否則繼續(xù)遞歸的搜索node的左右兩個子樹。

為了保證棧中存儲的是根節(jié)點到當(dāng)前遍歷節(jié)點的路徑，左右子樹搜索完成后，將node從棧中彈出。

在主函數(shù)lowestCommonAncestor中，定義存儲p、q路徑的vector，p_path和q_path。定義求節(jié)點路徑時使用的棧stack。

這里要說明的是，因為需要將棧中的內(nèi)容賦值給p_path和q_path，所以我們使用vector來實現(xiàn)棧。

調(diào)用dfs求出p和q的路徑，在完成p路徑的搜索時，需要將stack清空，再用其尋找q節(jié)點路徑。完成路徑的計算后，設(shè)置指針common存儲兩節(jié)點的最近公共祖先。

然后進入while循環(huán)，遍歷兩個節(jié)點的路徑，在循環(huán)中，尋找兩條路徑上最后一個相同的節(jié)點，將它存儲至common，最后函數(shù)返回common。

那么到這里，二叉樹中兩節(jié)點的最近公共祖先就講完了，感謝大家的觀看，我們下節(jié)課再會。