1. 題目

描述

給定一棵二叉樹(保證非空)以及這棵樹上的兩個節點對應的val值 o1 和 o2，請找到 o1 和 o2 的最近公共祖先節點。

數據範圍：樹上節點數滿足 1≤n≤10^5^ , 節點值val滿足區間 [0,n)

要求：時間複雜度 O(n)

注：本題保證二叉樹中每個節點的val值均不相同。

如當輸入{3,5,1,6,2,0,8,#,#,7,4},5,1時，二叉樹{3,5,1,6,2,0,8,#,#,7,4}如下圖所示：

所以節點值為5和節點值為1的節點的最近公共祖先節點的節點值為3，所以對應的輸出為3。

節點本身可以視為自己的祖先

示例1

輸入：

{3,5,1,6,2,0,8,#,#,7,4},5,1

返回值：

3

示例2

輸入：

{3,5,1,6,2,0,8,#,#,7,4},2,7

返回值：

2

2. 解題思路

本題求解的是普通二叉樹的公共祖先，即二叉樹的節點值沒有規律性（與二叉搜索樹不同），因此只能分不同情況進行處理：

情況1：節點的值等於給定的值（滿足給定的值p或q之一即可），該節點就是最近公共祖先

情況2：節點的值不等於給定的值，這時只能從左右子樹中查找：

1. 從節點的左子樹中找；
2. 從節點的右子樹中找；

3. 返回對應的節點：

   ①如果左右子樹的結果都為null，返回null（説明左右子樹中都沒有公共祖先）；

   ②左子樹或右子樹的結果有一個為null，返回不為null的結果（説明公共祖先存在於不為空的子樹中）；

   ③左右子樹的結果都不為空，返回當前節點（説明當前節點為公共祖先）。

採用遞歸的方式查找公共祖先節點。

遞推公式如下：

如果文字描述的不太清楚，你可以參考視頻的詳細講解。

• Python版本：https://www.bilibili.com/cheese/play/ep1372246
• Java版本：https://www.bilibili.com/cheese/play/ep1367354
• Golang版本：https://www.bilibili.com/cheese/play/ep1364779

3. 編碼實現

核心代碼如下：

/**
 * 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
 *
 *
 * @param root TreeNode類
 * @param o1 int整型
 * @param o2 int整型
 * @return int整型
 */
func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
    // write code here
    return recursion(root, o1, o2).Val
}

func recursion(root *TreeNode, v1 int, v2 int) *TreeNode {
    // 2. 遞歸終止條件：節點為空，直接返回
    if root == nil {
        return nil
    }

    // 1. 問題分解（遞推公式）
    // 1.1 節點的值等於給定的值，該節點就是最近公共祖先
    if root.Val == v1 || root.Val == v2 {
        return root
    }
    // 1.2 節點的值不等於給定的值
    // 1.2.1 到左子樹中找
    left := recursion(root.Left, v1, v2)
    // 1.2.2 到右子樹中找
    right := recursion(root.Right, v1, v2)
    // 1.2.3 返回節點
    if left == nil && right == nil {
        //左右子樹都沒有找到，返回nil
        return nil
    } else if left == nil && right != nil {
        //左子樹都沒有找到，右子樹找到，返回右子樹
        return right
    } else if left != nil && right == nil {
        //右子樹都沒有找到，左子樹找到，返回左子樹
        return left
    } else {
        //左右子樹都找到，返回當前節點
        return root
    }
}

具體完整代碼你可以參考下面視頻的詳細講解。

• Python版本：https://www.bilibili.com/cheese/play/ep1372246
• Java版本：https://www.bilibili.com/cheese/play/ep1367354
• Golang版本：https://www.bilibili.com/cheese/play/ep1364779

4.小結

普通二叉樹公共祖先的查找需要從左右子樹中分別查找，再依據查找的結果進行判斷：如果左右子樹有一個子樹查找到，則返回對應的子樹；如果都查找到則返回當前的節點（當前節點就是公共祖先）；如果都沒有查找到，則返回Null。

《數據結構與算法》深度精講課程正式上線啦！七大核心算法模塊全解析：

  ✅   鏈表

  ✅   二叉樹

  ✅   二分查找、排序

  ✅   堆、棧、隊列

  ✅   回溯算法

  ✅   哈希算法

  ✅   動態規劃

無論你是備戰筆試面試、提升代碼效率，還是突破技術瓶頸，這套課程都將為你構建紮實的算法思維底座。🔥立即加入學習打卡，與千名開發者共同進階！

• Python編碼實現：https://www.bilibili.com/cheese/play/ss897667807
• Java編碼實現：https://www.bilibili.com/cheese/play/ss161443488
• Golang編碼實現：https://www.bilibili.com/cheese/play/ss63997

對於二叉樹的相關算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易於理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。

今日佳句：北方有佳人，絕世而獨立。一顧傾人城，再顧傾人國。