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