題目描述

給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。

百度百科中最近公共祖先的定義為：“對(duì)于有根樹(shù) T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）。”

例如，給定如下二叉樹(shù): root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 1 的最近公共祖先是節(jié)點(diǎn) 3。
示例 2:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 4 的最近公共祖先是節(jié)點(diǎn) 5。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。

說(shuō)明:
所有節(jié)點(diǎn)的值都是唯一的。
p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉樹(shù)中。

題目分析

做了一些二叉樹(shù)的題，發(fā)現(xiàn)二叉樹(shù)的查找問(wèn)題一般都是從左右子樹(shù)遞歸去解決，也往往都能得到答案，因此，這道題可以考慮是否能從左右子樹(shù)進(jìn)行遞歸去解決呢？
首先，要想通過(guò)遞歸來(lái)實(shí)現(xiàn)，就需要先確定臨界條件，那么臨界條件是什么呢？換句話說(shuō)，臨界條件就是遞歸中能夠直接返回的特殊情況，第一點(diǎn)則是最常見(jiàn)的“判空”，判斷根結(jié)點(diǎn)是否是空節(jié)點(diǎn)，如果是，那么肯定就可以馬上返回了，這是一個(gè)臨界條件；再來(lái)考慮題意，在以root為根結(jié)點(diǎn)的樹(shù)中找到p結(jié)點(diǎn)和q結(jié)點(diǎn)的最近公共祖先，那么特殊情況是什么呢？很顯然，特殊情況就是根結(jié)點(diǎn)就等于q結(jié)點(diǎn)或p結(jié)點(diǎn)的情況，想一下，如果根結(jié)點(diǎn)為二者之一，那么根結(jié)點(diǎn)就必定是最近公共祖先了，這時(shí)直接返回root即可。由此看來(lái)，這道題就一共有三種特殊情況，root == q 、root == p和root==null，這三種情況均直接返回root即可。
根據(jù)臨界條件，實(shí)際上可以發(fā)現(xiàn)這道題已經(jīng)被簡(jiǎn)化為查找以root為根結(jié)點(diǎn)的樹(shù)上是否有p結(jié)點(diǎn)或者q結(jié)點(diǎn)，如果有就返回p結(jié)點(diǎn)或q結(jié)點(diǎn)，否則返回null。
這樣一來(lái)其實(shí)就很簡(jiǎn)單了，從左右子樹(shù)分別進(jìn)行遞歸，即查找左右子樹(shù)上是否有p結(jié)點(diǎn)或者q結(jié)點(diǎn)，就一共有4種情況：
第一種情況：左子樹(shù)和右子樹(shù)均找沒(méi)有p結(jié)點(diǎn)或者q結(jié)點(diǎn)；（這里特別需要注意，雖然題目上說(shuō)了p結(jié)點(diǎn)和q結(jié)點(diǎn)必定都存在，但是遞歸的時(shí)候必須把所有情況都考慮進(jìn)去，因?yàn)轭}目給的條件是針對(duì)于整棵樹(shù)，而遞歸會(huì)到局部，不一定都滿足整體條件）
第二種情況：左子樹(shù)上能找到，但是右子樹(shù)上找不到，此時(shí)就應(yīng)當(dāng)直接返回左子樹(shù)的查找結(jié)果；
第三種情況：右子樹(shù)上能找到，但是左子樹(shù)上找不到，此時(shí)就應(yīng)當(dāng)直接返回右子樹(shù)的查找結(jié)果；
第四種情況：左右子樹(shù)上均能找到，說(shuō)明此時(shí)的p結(jié)點(diǎn)和q結(jié)點(diǎn)分居root結(jié)點(diǎn)兩側(cè)，此時(shí)就應(yīng)當(dāng)直接返回root結(jié)點(diǎn)了。
綜上也不難寫(xiě)出結(jié)果了：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==p||root==q||!root)return root;TreeNode* left=lowestCommonAncestor(root->left, p, q);TreeNode* right=lowestCommonAncestor(root->right, p, q);if(!left&&!right)return NULL;else if(left&&!right)return left;else if(right&&!left)return right;return root;}

總結(jié)

以上是生活随笔為你收集整理的剑指 Offer 68 - II. （二叉树）二叉树的最近公共祖先的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。