一、題目

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

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

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

二、分析

本題需要找公共祖先，如果可以從下往上查找，就可以很方便的找到公共祖先

所以需要先訪問葉子節(jié)點(diǎn)，然后在往上訪問，對(duì)應(yīng)著二叉樹的后序遍歷

具體的判斷：如果找到一個(gè)節(jié)點(diǎn)，發(fā)現(xiàn)它的左子樹出現(xiàn) p，右子樹出現(xiàn) q，或者左子樹出現(xiàn) q，右子樹出現(xiàn) p，那么該節(jié)點(diǎn)就是節(jié)點(diǎn) p 和 q 的最近公共祖先

（1）確定遞歸參數(shù)和返回值

lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)

（2）確定遞歸終止條件

如果找到了節(jié)點(diǎn) p 或者節(jié)點(diǎn) q，或者遇到空節(jié)點(diǎn)就返回

if (root == p || root == q || root == null) {
	return root;
}

（3）確定單層遞歸邏輯

本題有返回值，因?yàn)榛厮莸倪^程需要遞歸函數(shù)的返回值做判斷，但本題依然需要遍歷樹的所有節(jié)點(diǎn)

那么為什么要遍歷整顆樹呢？直觀上來看，找到最近公共祖先，直接一路返回就可以了。

但事實(shí)上還要遍歷根節(jié)點(diǎn)右子樹（即使此時(shí)已經(jīng)找到了目標(biāo)節(jié)點(diǎn)了），也就是圖中的節(jié)點(diǎn)4、15、20。

因?yàn)樵谌缦麓a的后序遍歷中，如果想利用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 都不為空，說明此時(shí) root 就是最近公共節(jié)點(diǎn)。這個(gè)比較好理解

如果 left 為空，right 不為空，就返回 right，說明目標(biāo)節(jié)點(diǎn)是通過 right 返回的，反之依然

圖中節(jié)點(diǎn)10的左子樹返回null，右子樹返回目標(biāo)值7，那么此時(shí)節(jié)點(diǎn)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é)點(diǎn)的！

三、代碼

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //遞歸終止條件
        if (root == p || root == q || root == null) {
            return root;
        }
        //后序遍歷邏輯：遍歷左子樹，遍歷右子樹
        //有返回值，需要對(duì)返回值進(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;
    }
}

精簡(jiǎn)代碼：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //遞歸終止條件
        if (root == p || root == q || root == null) {
            return root;
        }
        //后序遍歷邏輯：遍歷左子樹，遍歷右子樹
        //有返回值，需要對(duì)返回值進(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ù)有返回值時(shí)，需要區(qū)分要搜索一條邊，還是搜索整個(gè)樹

搜索一條邊：

if (遞歸函數(shù)(root->left)) return ;
if (遞歸函數(shù)(root->right)) return ;

搜索整個(gè)樹：

left = 遞歸函數(shù)(root->left);
right = 遞歸函數(shù)(root->right);
left與right的邏輯處理;

在遞歸函數(shù)有返回值的情況下： 如果要搜索一條邊，遞歸函數(shù)返回值不為空的時(shí)候，立刻返回，如果搜索整個(gè)樹，直接用一個(gè)變量left、right接住返回值，這個(gè)left、right后序還有邏輯處理的需要，也就是后序遍歷中處理中間節(jié)點(diǎn)的邏輯（也是回溯）」

（1）求最小公共祖先，需要從底向上遍歷，那么二叉樹，只能通過后序遍歷（即：回溯）實(shí)現(xiàn)從低向上的遍歷方式

（2）在回溯的過程中，必然要遍歷整顆二叉樹，即使已經(jīng)找到結(jié)果了，依然要把其他節(jié)點(diǎn)遍歷完，因?yàn)橐褂眠f歸函數(shù)的返回值（也就是代碼中的left和right）做邏輯判斷

（3）要理解如果返回值left為空，right不為空為什么要返回right，為什么可以用返回right傳給上一層結(jié)果

好了，到此這篇關(guān)于Java求解二叉樹的最近公共祖先的文章就介紹到這了,更多相關(guān)Java求解二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論