一荧缘、題目
給定一個(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)也可以是它自己的祖先）。
二蜂奸、示例
2.1> 示例 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.2> 示例 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ù)中碌奉。
三短曾、解題思路
根據(jù)題目描述，會(huì)給我們兩個(gè)節(jié)點(diǎn)赐劣，分別是TreeNode p和TreeNode q，然后我們需要在一個(gè)二叉樹(shù)中去尋找著兩個(gè)給定節(jié)點(diǎn)的最近公共祖先哩都。這個(gè)題與《劍指 Offer 68 - I. 二叉搜索樹(shù)的最近公共祖先》很類(lèi)似魁兼，只不過(guò)我們這個(gè)樹(shù)是普通的二叉樹(shù)，不能利用二叉搜索樹(shù)的特性來(lái)解題了漠嵌。
那么我們知道咐汞，針對(duì)某一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，它是具有左子樹(shù)和右子樹(shù)這兩個(gè)屬性的儒鹿，那么對(duì)于隨機(jī)給出的p節(jié)點(diǎn)和q節(jié)點(diǎn)來(lái)說(shuō)化撕，就會(huì)有如下3種情況，請(qǐng)見(jiàn)下圖所示：
根據(jù)上圖描述约炎，我們可以得出如下3種情況：
【情況1】當(dāng)
p節(jié)點(diǎn)和q節(jié)點(diǎn)分別在根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)中時(shí)植阴，那么根節(jié)點(diǎn)就是最近公共祖先節(jié)點(diǎn)。
【情況2】當(dāng)p節(jié)點(diǎn)和q節(jié)點(diǎn)都在根節(jié)點(diǎn)的左子樹(shù)中時(shí)圾浅，第一個(gè)遍歷到的節(jié)點(diǎn)就是最近公共祖先節(jié)點(diǎn)掠手。
【情況3】當(dāng)p節(jié)點(diǎn)和q節(jié)點(diǎn)都在根節(jié)點(diǎn)的右子樹(shù)中時(shí)，第一個(gè)遍歷到的節(jié)點(diǎn)就是最近公共祖先節(jié)點(diǎn)狸捕。
所以喷鸽，針對(duì)上面的分析，我們可以通過(guò)深度遍歷來(lái)遍歷二叉樹(shù)中的節(jié)點(diǎn)灸拍，當(dāng)發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)等于p節(jié)點(diǎn)或者等于q節(jié)點(diǎn)做祝，則終止這一側(cè)子樹(shù)的遍歷砾省。然后當(dāng)根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都遍歷完畢后，再根據(jù)以上3種情況混槐，返回這道題的最終結(jié)果即可编兄。
解題思路我們說(shuō)完了，下面還是按照慣例纵隔，以輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 8為例翻诉，看一下具體處理流程是怎么樣子的。請(qǐng)見(jiàn)下圖所示：
四捌刮、代碼實(shí)現(xiàn)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return null;
TreeNode ln = lowestCommonAncestor(root.left, p, q);
TreeNode rn = lowestCommonAncestor(root.right, p, q);
return (ln != null && rn != null) ? root : (ln != null ? ln : rn);
}
}
今天的文章內(nèi)容就這些了：
寫(xiě)作不易碰煌，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章，只愿換來(lái)您幾秒鐘的 點(diǎn)贊 & 分享 绅作。
更多技術(shù)干貨芦圾，歡迎大家關(guān)注公眾號(hào)“爪哇繆斯” ~ \(o)/ ~ 「干貨分享，每天更新」
