求解最近公共祖先的算法

分為兩個(gè)步驟：

1. 求出兩節(jié)點(diǎn)路徑
2. 取兩路徑上最后一個(gè)相同的節(jié)點(diǎn)（該節(jié)點(diǎn)即為p，q節(jié)點(diǎn)的最近公共祖先）

節(jié)點(diǎn)路徑的算法設(shè)計(jì)與實(shí)現(xiàn)

求節(jié)點(diǎn)路徑即輸入二叉樹根節(jié)點(diǎn)與待求節(jié)點(diǎn)返回根節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)。

具體有如下幾個(gè)要點(diǎn)：

1. 我們需要設(shè)置一個(gè)棧，存儲(chǔ)最終的節(jié)點(diǎn)路徑。找到該節(jié)點(diǎn)時(shí)，從棧底到棧頂存儲(chǔ)的節(jié)點(diǎn)即為從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑。
   
2. 需要通過(guò)遍歷算法，從根節(jié)點(diǎn)遍歷至該節(jié)點(diǎn)。樹的遍歷算法可以是遞歸的深度優(yōu)先搜索算法。找到該節(jié)點(diǎn)后就結(jié)束搜索。
   
3. 將遍歷過(guò)程中遇到的節(jié)點(diǎn)按照順序存儲(chǔ)到棧中。節(jié)點(diǎn)遍歷完成之后需要彈出棧，從而保證棧中存儲(chǔ)的節(jié)點(diǎn)時(shí)根節(jié)點(diǎn)到當(dāng)前遍歷節(jié)點(diǎn)路徑上的節(jié)點(diǎn)。
   
   
   

具體代碼

深度優(yōu)先搜索尋找路徑上的節(jié)點(diǎn)

利用兩節(jié)點(diǎn)的路徑尋找最近公共祖先

測(cè)試主程序

參考資料：
算法與數(shù)據(jù)結(jié)構(gòu)，二叉樹，程序員面試高頻題，最近的公共祖先