- 博主簡介：努力學習的22級計算機科學與技術(shù)本科生一枚??
- 博主主頁： @是瑤瑤子啦
- 每日一言??: 你不能要求一片海洋，沒有風暴，那不是海洋，是泥塘——畢淑敏
一、題目
??236. 二叉樹的最近公共祖先
二、題解
注意：祖先是包括自身的！
-
??首先要明白，當root為p,q的最近祖先節(jié)點，只有下面3種情況：
1. p，q在root分別存在于root的左右子樹中（異側(cè)）——>root即為最近祖先節(jié)點
2. p, q均在root的左側(cè)——>p/q即為最近祖先節(jié)點
3. p, q均在root的右側(cè)——>同理
-
??遞歸函數(shù)的定義
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)：在以root為根節(jié)點的樹中找并且返回p和q的最近的祖先節(jié)點。
1.終止條件：- root == null；return null
-
root = = p或者root = = q，直接返回p/q
2.遞推工作：（到這里說明此時p和q要么在此次遞歸的root的同側(cè)或者異側(cè)）left 用于記錄在左側(cè)進行尋找公共祖先（這里的遞歸函數(shù)作用就是單純找q/p節(jié)點并且找到就返回的作用了，當然你可以另外寫一個找節(jié)點的函數(shù)，但是沒必要，因為定義的遞歸函數(shù)本身就能實現(xiàn)這個功能），right同理
-
left和right均為null，說明root的左右都沒有p,q，那就不存在公共節(jié)點，返回Null（有點扯，按理來說，p,q肯定是存在的，但是特判一下也不虧）
-
?left和right均不空，說明在此時遞歸情況是：p,q在
root異側(cè)，那么直接返回root即可
3. ?left不為空,right為空;right不為空，left為空。直接將不為空的那個返回即可！此時不為空的left/right指向的就是最近祖先節(jié)點。
三、代碼
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right !=null){
return root;
}else if(left == null){
return right;
}else if(right == null){
return left;
}else{
return null;
}
}
??若有不懂的地方，歡迎隨時在評論區(qū)or私信找瑤瑤子交流討論??
-
Java島冒險記【從小白到大佬之路】
-
LeetCode每日一題–進擊大廠
-
Go語言核心編程
文章來源：http://www.zghlxwxcb.cn/news/detail-650621.html -
算法文章來源地址http://www.zghlxwxcb.cn/news/detail-650621.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹篇|超清晰圖解和詳解：二叉樹的最近公共祖先的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
