Java求解二叉樹的最近公共祖先實例代碼
一、題目
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”
例如，給定如下二叉樹: 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)文章
Spring MVC全局異常處理和單元測試_動力節(jié)點Java學(xué)院整理
本篇文章主要介紹了Spring MVC全局異常處理和單元測試，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-08-08
這篇文章主要介紹了Java網(wǎng)絡(luò)編程入門，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
SpringBoot如何使用@Value取配置文件中的map配置
這篇文章主要介紹了SpringBoot如何使用@Value取配置文件中的map配置方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-05-05
使用IDEA搭建SSM框架的詳細(xì)教程(spring + springMVC +MyBatis)
這篇文章主要介紹了使用IDEA搭建SSM框架的詳細(xì)教程 spring + springMVC +MyBatis,本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-05-05
SpringBoot中的時間格式化通常指的是將Java中的日期時間類型轉(zhuǎn)換為指定格式的字符串,或者將字符串類型的時間解析為Java中的日期時間類型,本文小編將給大家詳細(xì)總結(jié)了SpringBoot時間格式化的方法,剛興趣的小伙伴跟著小編一起來看看吧2023-10-10
mybatis-plus enum實現(xiàn)枚舉類型自動轉(zhuǎn)換
本文主要介紹了mybatis-plus enum實現(xiàn)枚舉類型自動轉(zhuǎn)換,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-07-07
這篇文章主要介紹了java中的動態(tài)代理與責(zé)任鏈模式詳解,動態(tài)代理提供了一種靈活且非侵入式的方式,可以對對象的行為進(jìn)行定制和擴(kuò)展,它在代碼重用、解耦和業(yè)務(wù)邏輯分離、性能優(yōu)化以及系統(tǒng)架構(gòu)中起到了重要的作用,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了Spring Cloud Feign報錯問題解決,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-12-12
Maven安裝本地的jar包和創(chuàng)建帶模板的自定義項目的操作過程
這篇文章主要介紹了Maven安裝本地的jar包和創(chuàng)建帶模板的自定義項目,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友參考下吧2024-03-03
這篇文章主要介紹了JAVA 虛引用的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)JAVA，感興趣的朋友可以了解下2020-08-08