題目
#

leetcode 235 - Lowest Common Ancestor of a Binary Search Tree (題目說明請點連結)

題目簡述
#

給一個二元搜尋樹（Binary Search Tree）的根節點 root 和兩個節點 p 和 q，請找出這兩個節點的最低共同祖先（Lowest Common Ancestor, LCA）。
最低共同祖先是指在樹中距離 p 和 q 最近的共同祖先節點。一個節點也可以是它自己的祖先。

範例
#

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: 節點 2 和 8 的最低共同祖先是節點 6。

graph TD; A[6] B[2] C[8] D[0] E[4] F[7] G[9] H[3] I[5] A --> B A --> C B --> D B --> E C --> F C --> G E --> H E --> I style A fill:#90EE90 style B fill:#FFB6C1 style C fill:#FFB6C1

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: 節點 2 和 4 的最低共同祖先是節點 2，因為節點 2 是節點 4 的祖先。

graph TD; A[6] B[2] C[8] D[0] E[4] F[7] G[9] H[3] I[5] A --> B A --> C B --> D B --> E C --> F C --> G E --> H E --> I style B fill:#90EE90 style B fill:#FFB6C1 style E fill:#FFB6C1

解題思路
#

這題要求我們在二元搜尋樹（BST）中找到兩個節點的最低共同祖先（LCA）。由於 BST 的特性，我們可以利用節點值的大小關係來快速定位 LCA，而不需要遍歷整個樹。

解法
#

利用 BST 的特性：左子樹的所有節點值都小於根節點，右子樹的所有節點值都大於根節點
比較當前節點值與 p 和 q 的值
如果當前節點值大於 p 和 q 的值，LCA 在左子樹
如果當前節點值小於 p 和 q 的值，LCA 在右子樹
否則，當前節點就是 LCA

步驟
#

邊界條件：
- 如果根節點為空，返回 null
BST 特性判斷：
- 如果根節點值大於 p 和 q 的值，遞迴搜尋左子樹
- 如果根節點值小於 p 和 q 的值，遞迴搜尋右子樹
- 否則，返回根節點（即 LCA）

例子說明
#

root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

graph TD; A[6] B[2] C[8] D[0] E[4] F[7] G[9] H[3] I[5] A --> B A --> C B --> D B --> E C --> F C --> G E --> H E --> I style A fill:#90EE90 style B fill:#FFB6C1 style C fill:#FFB6C1

步驟	當前節點	節點值	p 值	q 值	比較結果	下一步
第 1 步	6	6	2	8	6 > 2 且 6 < 8	6 是 LCA，返回 6

最終結果： 6

LCA 判斷過程說明：

節點 6：p = 2 < 6 < q = 8
- 由於 6 的值在 2 和 8 之間，且 2 在左子樹，8 在右子樹
- 因此節點 6 是節點 2 和 8 的最低共同祖先

BST 特性應用：

左子樹：包含值小於 6 的節點（0, 2, 3, 4, 5）
右子樹：包含值大於 6 的節點（7, 8, 9）
LCA 條件：當一個節點的值在 p 和 q 的值之間時，該節點就是 LCA

完整程式碼
#

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 邊界條件：如果根節點為空，返回 null
        if(root == null) {
            return null;
        }

        // 利用 BST 特性來快速定位 LCA
        if(root.val > p.val && root.val > q.val){
            // 如果根節點值大於 p 和 q 的值，LCA 在左子樹
            return lowestCommonAncestor(root.left, p, q);
        } else if(root.val < p.val && root.val < q.val){
            // 如果根節點值小於 p 和 q 的值，LCA 在右子樹
            return lowestCommonAncestor(root.right, p, q);
        } else {
            // 否則，當前節點就是 LCA
            // 這種情況包括：
            // 1. root.val 在 p.val 和 q.val 之間
            // 2. root.val 等於 p.val 或 q.val
            return root;
        }
    }
}

時間複雜度
#

時間複雜度：O(h)，其中 h 是樹的高度
- 最壞情況下需要從根節點遍歷到葉節點
- 對於平衡的 BST，時間複雜度為 O(log n)
- 對於不平衡的 BST，時間複雜度為 O(n)
空間複雜度：O(h)，其中 h 是樹的高度
- 遞迴調用棧的深度等於樹的高度
- 對於平衡的 BST，空間複雜度為 O(log n)
- 對於不平衡的 BST，空間複雜度為 O(n)