Java求解二叉樹中最近公共祖先的示例分析

小編給大家分享一下Java求解二叉樹中最近公共祖先的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

一、題目

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

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

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

二、分析

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

所以需要先訪問葉子節點，然后在往上訪問，對應著二叉樹的后序遍歷

具體的判斷：如果找到一個節點，發現它的左子樹出現 p，右子樹出現 q，或者左子樹出現 q，右子樹出現 p，那么該節點就是節點 p 和 q 的最近公共祖先

（1）確定遞歸參數和返回值

lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)

（2）確定遞歸終止條件

如果找到了節點 p 或者節點 q，或者遇到空節點就返回

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

（3）確定單層遞歸邏輯

本題有返回值，因為回溯的過程需要遞歸函數的返回值做判斷，但本題依然需要遍歷樹的所有節點

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

但事實上還要遍歷根節點右子樹（即使此時已經找到了目標節點了），也就是圖中的節點4、15、20。

因為在如下代碼的后序遍歷中，如果想利用left和right做邏輯處理， 不能立刻返回，而是要等left與right邏輯處理完之后才能返回。

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

那么先用left和right接住左子樹和右子樹的返回值，代碼如下：

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

如果 left 和 right 都不為空，說明此時 root 就是最近公共節點。這個比較好理解

如果 left 為空，right 不為空，就返回 right，說明目標節點是通過 right 返回的，反之依然

圖中節點10的左子樹返回null，右子樹返回目標值7，那么此時節點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;

那么尋找最小公共祖先，完整流程圖如下：

從圖中可以看到回溯遍歷整顆二叉樹，將結果返回給頭結點的！

三、代碼

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

四、總結

遞歸函數有返回值時，需要區分要搜索一條邊，還是搜索整個樹

搜索一條邊：

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

搜索整個樹：

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

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

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

（2）在回溯的過程中，必然要遍歷整顆二叉樹，即使已經找到結果了，依然要把其他節點遍歷完，因為要使用遞歸函數的返回值（也就是代碼中的left和right）做邏輯判斷

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

以上是“Java求解二叉樹中最近公共祖先的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！