二叉樹的最近公共祖先
文章目錄
-
- 一、題目描述
- 二、解題思路
- 三、代碼解析
一、題目描述
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。
以上面這個圖為例子：
5和1 的最近公共祖先就是3。
二、解題思路
剛看到這個題，肯定會有點懵，我開始也很懵，根本不知道從何下手，沒關系，隻需要先将這個思路了解了，先将這個方法掌握啦，掌握的方法多了，慢慢就有了自己的思路了。
用什麼周遊序列？
這題要問的是給定p,q的最近公共祖先。很明顯，是找指定孩子結點的祖先結點。
那麼，我們是不是應該先檢查子孫，通過檢查子孫傳回的結果來判斷目前結點是否是目标結點。
比如上面的例子，最後傳回的是3，這個3是我們在檢查完5和1後，發現5和1滿足條件才認定3是最終結果的。
那麼請問大家，用哪個周遊順序？
A:中左右
B:左中右
C:左右中
答案明顯是：C
根據周遊左右子樹的結果來判斷目前結點是不是要求的結點。
怎麼用後序周遊解決這個問題？
首先考慮，我們對于每一個結點的左右子樹應該傳回什麼内容，才能讓判斷這個結點是否是最近公共祖先？
還是剛才的例子，
我們發現3->left是5滿足給定的p=5
我們發現3->right是1滿足給定的q=1
是以，我們認為3是5,1的公共祖先。
那如果要求
p = 6
,
q = 1
的最近公共祖先呢？
明顯能看出來，6和1的最近公共祖先還是3。
那是怎麼判斷的呢？
遞歸周遊3的左子樹，如果左子樹出現目标p或者q，就p或者q一層層傳回上來。
周遊5的時候，如果5的左子樹或者右子樹出現p或者q，就傳回上來。
總之：
無論在這個樹的哪個位置找到了p或者q都要能把p,q傳回到上一層，友善上層結點做判斷。
是以說，遞歸函數傳回值，傳回的就是這個子樹中是否有p,或者q。
如果有p或者q,就傳回p或者q,如果沒有就傳回
。NULL
怎麼通過左右子樹傳回的值判斷最終的結果呢?
左右子樹返會值會出現那些情況，有那些值是我們要傳回的?
首先，如果遇到p,q肯定要傳回。
其次，如果找到了【最近公共祖先】肯定也要傳回
再次，如果不是上面兩種情況，傳回NULL就行了。
三、代碼解析
看了上面的解析，可能還有點懵，那下面再結合具體代碼了解
template<class T>
TreeNode<T>* lowestCommonAncestor(TreeNode<T>* root, TreeNode<T>* p, TreeNode<T>* q) {
//思路
/*
題目給了兩個二叉樹結點的指針，要傳回這兩個指針的最近的公共祖先。
首先，這個題隻能使用後序周遊，左右中。因為後序是先通路兩個葉子，再通路中間結點。
那根據後序周遊的通路順序怎麼操作呢？
我們将後序每個結點後序左右子樹周遊的結果儲存在left和right中。
如果有p那left儲存的就是p
(隻要左子樹出現p就，整個左子樹傳回的就是p，q同理，右子樹同理，如果p,q都沒有出現，就傳回NULL)
這樣，對每一個結點都可以得到這個結點左右子樹傳回來的值。
我們就根據這個結點左右子樹傳回來的值來判斷這個結點是不是p，q的最近公共結點。
怎麼判斷呢？左右子樹可能跟傳回如下三個值：p, q, NULL
那麼請問，一個結點的左右子樹滿足那種情況的時候，這個結點是p, q的最近公共祖先呢？
當然隻有兩種情況：left:q, right:p 和left:p, right:q這兩種情況了。
是以，這時候隻需要做判斷，如果左右子樹傳回的都不是NULL那麼，目前處理的這個結點就是p,q的最近公共祖先了。
結束。
*/
//1.傳回值和參數：傳回值仍然是Treenode
//2.遞歸終止的條件
/*什麼時候遞歸終止？
2.1 目前通路的結點是p或者q
2.2 目前通路到了空節點NULL(這個樹是空樹，或者葉子結點的孩子)
*/
if (root == q || root == p || root == NULL) return root;//對葉子結點的處理
//3.單層遞歸處理邏輯
//3.1 後序周遊左子樹
TreeNode<T>* left = lowestCommonAncestor(root->left, p, q);
//3.2 後序周遊右子樹
TreeNode<T>* right = lowestCommonAncestor(root->right, p, q);
//3.3 後序周遊進行中間結點
//問題：這裡為什麼判斷的是左右子樹傳回值不為NULL，為什麼不判斷左右子樹傳回值是p,q?
/*
因為，我們要向上傳遞的是四種值：NULL,p,q,最近公共祖先
如果，判斷是左右子樹傳回的是否是p,q那麼，如果左右子樹有一個子樹出現了【最近公共祖先】
那這個結果會因為不是p,q而傳遞不上去。
反之，我們之和NULL做比較，隻要不是NULL的都往上傳，那無論在哪裡找到了【最近公共祖先】
都會被遞歸傳回上去。
*/
//得到了這個結點左右子樹的值，就要判斷這個結點是不是p,q的最近公共結點了
if (left != NULL && right != NULL) return root;//左右子樹都不為空，說明左右子樹傳回的是p,q或者q,p具體順序我們不關心
if (left != NULL && right == NULL) return left;//一個不為空，傳回不為空的那個
else if (left == NULL && right != NULL) return right;//同理
else {
return NULL;//隻剩下最後一種情況，左右兩邊都傳回的是NULL
}
}