這是《劍指Offer——名企面試官精講典型編程題》一書中的面試題50，此題針對(duì)所給條件的不同，將需要截然不同的解題思路和方法。書中給出了針對(duì)此題的3種不同條件的解題，本文所要講解的是對(duì)其第3種條件的一個(gè)改進(jìn)解法。具體的題目及條件如下。
【題目】：
輸入兩個(gè)樹結(jié)點(diǎn)，求它們的最低公共祖先。
【補(bǔ)充條件】：
樹是普通的樹，而且樹中的結(jié)點(diǎn)沒有指向父節(jié)點(diǎn)的指針。
針對(duì)上述的題目和條件，書中給出了如下解決方案。
【原方案】：
使用兩個(gè)鏈表，對(duì)樹進(jìn)行兩次遍歷以查找兩個(gè)樹結(jié)點(diǎn)，并保持路徑到兩個(gè)鏈表中，從而將問題轉(zhuǎn)化為求兩個(gè)鏈表的最后一個(gè)公共結(jié)點(diǎn)。
從該方案中，觀察到兩次樹結(jié)點(diǎn)查找的遍歷中，其中一個(gè)結(jié)點(diǎn)的遍歷過的樹結(jié)點(diǎn)序列將完全覆蓋查找另一結(jié)點(diǎn)時(shí)所遍歷的樹結(jié)點(diǎn)序列。由此入手，本文提出了如下的改進(jìn)解決方案。
【改進(jìn)方案】：
深度優(yōu)先遍歷樹，并記錄路徑，當(dāng)找到第一個(gè)結(jié)點(diǎn)后，在當(dāng)前基礎(chǔ)上繼續(xù)遍歷搜索第二個(gè)結(jié)點(diǎn)，并記錄第一個(gè)結(jié)點(diǎn)路徑的變化程度，直到找到第二個(gè)結(jié)點(diǎn)。最后，根據(jù)棧信息和記錄的結(jié)點(diǎn)路徑變化程度得到最低公共祖先。如圖1，假設(shè)輸入的兩個(gè)樹結(jié)點(diǎn)為D和K，樹的根節(jié)點(diǎn)為R，則求D和K的最低公共結(jié)點(diǎn)的過程如下表：
|
步驟 |
棧 |
第一個(gè)結(jié)點(diǎn) |
第二個(gè)結(jié)點(diǎn) |
路徑變化程度 |
|
1 |
R |
— |
— |
— |
|
2 |
R，A |
— |
— |
— |
|
3 |
R，A，F |
— |
— |
— |
|
4 |
R，A，F，J |
— |
— |
— |
|
5 |
R，A，F，G |
— |
— |
— |
|
6 |
R，A，F，K |
K |
— |
0（或K） |
|
7 |
R，A，C |
K |
— |
1（或A） |
|
8 |
R，A，C，E |
K |
— |
2（或A） |
|
9 |
R，A，C，I |
K |
— |
2（或A） |
|
10 |
R，A，D |
K |
D |
1（或A） |
|
è 得出結(jié)果，最低公共祖先結(jié)點(diǎn)為A |
從中，可以看到，改進(jìn)后的方案，只需對(duì)樹執(zhí)行一次遍歷。而在輔助空間的需求上， 只需使用一個(gè)棧（外加少量結(jié)點(diǎn)指針變量和1個(gè)表示路徑變化程度的整型變量）。而且，如果采用遞歸的方式實(shí)現(xiàn)，該棧所需保存的信息，還可以通過遞歸時(shí)的函數(shù)調(diào)用棧得以保存。
【附注】：
- 此處，有如下一個(gè)問題：
假設(shè)待查找公共祖先的兩樹結(jié)點(diǎn)，其中一結(jié)點(diǎn)在以另一結(jié)點(diǎn)為根的子樹上（包括兩結(jié)點(diǎn)相同）時(shí)，公共祖先的確定規(guī)則——
“作為子樹根結(jié)點(diǎn)的那個(gè)結(jié)點(diǎn)”還是“子樹根結(jié)點(diǎn)的父節(jié)點(diǎn)”？
例如：對(duì)上面圖1中的那棵樹，如果待查結(jié)點(diǎn)為根結(jié)點(diǎn)R和結(jié)點(diǎn)F，那么最終的查找結(jié)果是為R呢，還是因?yàn)?/span>R是根結(jié)點(diǎn)無父結(jié)點(diǎn)而得出NULL？
此問題在書中未提及，但查看書中代碼，確認(rèn)是選擇了后者；而在本人的樣例代碼中則采用了前面的觀點(diǎn)。 - 在樣例代碼中，對(duì)樹結(jié)點(diǎn)在棧中的存儲(chǔ)方式略有改動(dòng)。
- 樣例代碼工程所使用的環(huán)境為 Visual C++ 2010；
其中：tree.h/cpp為功能代碼文件，TestLowestCommonAncestor.h/cpp為相應(yīng)的UT代碼文件；
UT采用gtest所編寫，編譯鏈接請(qǐng)根據(jù)gtest在自己本機(jī)的路徑狀況修改gtest_link.props文件中相應(yīng)的鏈接項(xiàng)。