Java求解二叉樹的最近公共祖先實例代碼
一、題目
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）?！?/p>
例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]
二、分析
本題需要找公共祖先，如果可以從下往上查找，就可以很方便的找到公共祖先
所以需要先訪問葉子節(jié)點，然后在往上訪問，對應(yīng)著二叉樹的后序遍歷
具體的判斷：如果找到一個節(jié)點，發(fā)現(xiàn)它的左子樹出現(xiàn) p，右子樹出現(xiàn) q，或者左子樹出現(xiàn) q，右子樹出現(xiàn) p，那么該節(jié)點就是節(jié)點 p 和 q 的最近公共祖先
（1）確定遞歸參數(shù)和返回值
lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
（2）確定遞歸終止條件
如果找到了節(jié)點 p 或者節(jié)點 q，或者遇到空節(jié)點就返回
if (root == p || root == q || root == null) {
return root;
}
（3）確定單層遞歸邏輯
本題有返回值，因為回溯的過程需要遞歸函數(shù)的返回值做判斷，但本題依然需要遍歷樹的所有節(jié)點
那么為什么要遍歷整顆樹呢？直觀上來看，找到最近公共祖先，直接一路返回就可以了。
但事實上還要遍歷根節(jié)點右子樹（即使此時已經(jīng)找到了目標(biāo)節(jié)點了），也就是圖中的節(jié)點4、15、20。
因為在如下代碼的后序遍歷中，如果想利用left和right做邏輯處理， 不能立刻返回，而是要等left與right邏輯處理完之后才能返回。
left = 遞歸函數(shù)(root->left); right = 遞歸函數(shù)(root->right); left與right的邏輯處理;
那么先用left和right接住左子樹和右子樹的返回值，代碼如下：
TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q);
如果 left 和 right 都不為空，說明此時 root 就是最近公共節(jié)點。這個比較好理解
如果 left 為空，right 不為空，就返回 right，說明目標(biāo)節(jié)點是通過 right 返回的，反之依然
圖中節(jié)點10的左子樹返回null，右子樹返回目標(biāo)值7，那么此時節(jié)點10的處理邏輯就是把右子樹的返回值（最近公共祖先7）返回上去！
那么如果left和right都為空，則返回left或者right都是可以的，也就是返回空。
if (left == null && right != null) {
return right;
}
if (left != null && right == null) {
return left;
}
if (left == null && right == null) {
return null;
}
return root;
那么尋找最小公共祖先，完整流程圖如下：
從圖中可以看到回溯遍歷整顆二叉樹，將結(jié)果返回給頭結(jié)點的！
三、代碼
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遞歸終止條件
if (root == p || root == q || root == null) {
return root;
}
//后序遍歷邏輯：遍歷左子樹，遍歷右子樹
//有返回值，需要對返回值進(jìn)行邏輯處理
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right != null) {
return right;
}
if (left != null && right == null) {
return left;
}
if (left == null && right == null) {
return null;
}
return root;
}
}
精簡代碼：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遞歸終止條件
if (root == p || root == q || root == null) {
return root;
}
//后序遍歷邏輯：遍歷左子樹，遍歷右子樹
//有返回值，需要對返回值進(jìn)行邏輯處理
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
if (left == null) {
return right;
}
return right;
}
}
四、總結(jié)
遞歸函數(shù)有返回值時，需要區(qū)分要搜索一條邊，還是搜索整個樹
搜索一條邊：
if (遞歸函數(shù)(root->left)) return ;
if (遞歸函數(shù)(root->right)) return ;
搜索整個樹：
left = 遞歸函數(shù)(root->left); right = 遞歸函數(shù)(root->right); left與right的邏輯處理;
在遞歸函數(shù)有返回值的情況下： 如果要搜索一條邊，遞歸函數(shù)返回值不為空的時候，立刻返回，如果搜索整個樹，直接用一個變量left、right接住返回值，這個left、right后序還有邏輯處理的需要，也就是后序遍歷中處理中間節(jié)點的邏輯（也是回溯）」
（1）求最小公共祖先，需要從底向上遍歷，那么二叉樹，只能通過后序遍歷（即：回溯）實現(xiàn)從低向上的遍歷方式
（2）在回溯的過程中，必然要遍歷整顆二叉樹，即使已經(jīng)找到結(jié)果了，依然要把其他節(jié)點遍歷完，因為要使用遞歸函數(shù)的返回值（也就是代碼中的left和right）做邏輯判斷
（3）要理解如果返回值left為空，right不為空為什么要返回right，為什么可以用返回right傳給上一層結(jié)果
好了，到此這篇關(guān)于Java求解二叉樹的最近公共祖先的文章就介紹到這了,更多相關(guān)Java求解二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
SpringBoot學(xué)習(xí)篇之@Valid與@Validated的區(qū)別
@Valid是使用Hibernate?validation的時候使用,@Validated是只用Spring?Validator校驗機制使用,下面這篇文章主要給大家介紹了關(guān)于SpringBoot學(xué)習(xí)篇之@Valid與@Validated區(qū)別的相關(guān)資料,需要的朋友可以參考下2022-11-11
緩存可以通過將經(jīng)常訪問的數(shù)據(jù)存儲在內(nèi)存中，減少底層數(shù)據(jù)源如數(shù)據(jù)庫的壓力，從而有效提高系統(tǒng)的性能和穩(wěn)定性。本文就來講講SpringBoot項目中使用緩存Cache的正確姿勢吧2023-04-04
這篇文章主要介紹了SpringIOC——DI循環(huán)依賴,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了Java設(shè)計模式之單例模式簡單解析,單例模式的優(yōu)點在于在內(nèi)存中某個類只有一個實例,減少了內(nèi)存的開銷,尤其是頻繁的創(chuàng)建和銷毀實例,避免對資源的多重暫用,需要的朋友可以參考下2023-12-12
MybatisPlusException:Failed?to?process,Error?SQL異常報錯的解決辦法
這篇文章主要給大家介紹了關(guān)于MybatisPlusException:Failed?to?process,Error?SQL異常報錯的解決辦法,文中通過實例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2023-03-03
SpringMVC整合,出現(xiàn)注解沒有起作用的情況處理
這篇文章主要介紹了SpringMVC整合,出現(xiàn)注解沒有起作用的情況及處理，具有很好的參考價值，希望對大家有所幫助。2023-05-05
本文主要介紹了springboot接入mq的方法示例,主要實現(xiàn)配置以及實現(xiàn)一個簡單的發(fā)送、接收消息的例子,具有一定的參考價值,感興趣的可以了解一下2023-09-09
通常我們在項目中引入第三方依賴包時,為了避免其版本迭代問題,經(jīng)常會使用本地的包，這篇文章主要給大家介紹了關(guān)于maven加載依賴報錯的原因分析及解決方法的相關(guān)資料,需要的朋友可以參考下2023-10-10
這篇文章主要給大家介紹了關(guān)于IDEA中maven依賴報紅的問題解決辦法,在使用IDEA過程中,經(jīng)常會出現(xiàn)maven依賴報紅的問題,文中通過圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-07-07
這篇文章主要介紹了Run Length編碼的一個示例，大家參考使用吧2014-01-01