1. 題目

描述

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

1.對於該題的最近的公共祖先定義:對於有根樹T的兩個節點p、q，最近公共祖先LCA(T,p,q)表示一個節點x，滿足x是p和q的祖先且x的深度儘可能大。在這裏，一個節點也可以是它自己的祖先.

2.二叉搜索樹是若它的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值； 若它的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值

3.所有節點的值都是唯一的。

4.p、q 為不同節點且均存在於給定的二叉搜索樹中。

數據範圍:

3<=節點總數<=10000

0<=節點值<=10000

如果給定以下搜索二叉樹: {7,1,12,0,4,11,14,#,#,3,5}，如下圖:

示例1

輸入：

{7,1,12,0,4,11,14,#,#,3,5},1,12

返回值：

7

説明：

節點1 和 節點12的最近公共祖先是7   

示例2

輸入：

{7,1,12,0,4,11,14,#,#,3,5},12,11

返回值：

12

説明：

因為一個節點也可以是它自己的祖先.所以輸出12   

2. 解題思路

先來看一下二叉搜索樹的性質：

二叉搜索樹（Binary Search Tree）、二叉查找樹（Binary Search Tree）和二叉排序樹（Binary Sort Tree）是同一個概念的不同稱呼，它們都是指一種特殊類型的二叉樹。這種樹具有以下特性：

1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值。
2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值。
3. 任意節點的左、右子樹也分別為二叉搜索樹（或二叉查找樹、二叉排序樹）。

整體思路為：

對於給定的值p、q：

①如果節點的值大於p,q則公共祖先在左子樹；

②如果節點的值小於p,q,則公共祖先在右子樹；

③如果節點的值在p、q對應的區間內，則當前節點就是公共祖先。

採用遞歸的方式對查找公共祖先。遞推公式如下：

有了遞推公式，就可以很方便的寫出對應方代碼。

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

• Python版本：https://www.bilibili.com/cheese/play/ep1372245
• Java版本：https://www.bilibili.com/cheese/play/ep1367353
• Golang版本：https://www.bilibili.com/cheese/play/ep1364778

3. 編碼實現

核心代碼如下：

/**
 * 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
 *
 *
 * @param root TreeNode類
 * @param p int整型
 * @param q int整型
 * @return int整型
 */
func lowestCommonAncestor(root *TreeNode, p int, q int) int {
    // write code here
    // 2. 遞歸終止條件：空樹找不到公共祖先
    if root == nil {
        return -1
    }

    // 1. 問題分解（遞推公式）
    if root.Val > q && root.Val > p {
        // 1.1  pq都在節點的左邊，則：公共祖先在左子樹中
        return lowestCommonAncestor(root.Left, p, q)
    } else if root.Val < q && root.Val < p {
        // 1.2  pq都在節點的右邊，則：公共祖先在右子樹中
        return lowestCommonAncestor(root.Right, p, q)
    } else {
        // 1.3 節點的值在給定的區間，則：找到了公共祖先
        return root.Val
    }
}

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

• Python編碼：https://www.bilibili.com/cheese/play/ep1372245
• Java編碼：https://www.bilibili.com/cheese/play/ep1367353
• Golang編碼：https://www.bilibili.com/cheese/play/ep1364778

4.小結

依據二叉搜索樹的性質來求解公共祖先，對於給定的值p、q：①如果節點的值大於p,q則公共祖先在左子樹；②如果節點的值小於p,q,則公共祖先在右子樹；③如果節點的值在p、q對應的區間內，則當前節點就是公共祖先。

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

  ✅   鏈表

  ✅   二叉樹

  ✅   二分查找、排序

  ✅   堆、棧、隊列

  ✅   回溯算法

  ✅   哈希算法

  ✅   動態規劃

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

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

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

今日佳句：露從今夜白，月是故鄉明。