可視化圖解算法34：二叉搜索樹的最近公共祖先详情 - 二叉樹,數據結構,算法,leetcode,筆試 cqu_jiangzhou 日志

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

返回值：

説明：

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

示例2

輸入：

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

返回值：

説明：

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

2. 解題思路

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

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

若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值。

若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值。

任意節點的左、右子樹也分別為二叉搜索樹（或二叉查找樹、二叉排序樹）。

整體思路為：

對於給定的值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
    }
}

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