0235. Lowest Common Ancestor of a Binary Search Tree - chasel2361/leetcode GitHub Wiki

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
example1

Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
example2

Example 3:
Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints:
The number of nodes in the tree is in the range [2, 105].
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q
p and q will exist in the BST.

這題的重點在於找到距離最近的"共同的父節點"，我們可以從 Binary Search Tree 的特性來下手處理。
由於 BST 的子節點在儲存時會影響到儲存的位置，若子節點之值大於父節點，則子節點會位於父節點右側，若否則位於左側。
所以我們可以歸納出幾個條件：

  1. 若 p, q 其中一值等於當前之父節點，則當前父節點為最近的共同父節點
  2. 若 p, q 之值皆大於當前父節點，則共同父節點位於當前父節點之右側
  3. 若 p, q 之值皆小於當前父節點，則共同父節點位於當前父節點之左側

因此可以從以上三個條件來撰寫程式，一開始我用遞迴法來寫，程式碼如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        cond1 = root.val == p.val or root.val == q.val
        cond2 = p.val < root.val and root.val < q.val
        cond3 = p.val > root.val and root.val > q.val
        
        if cond1 or cond2 or cond3:
            return root
        if root.val > p.val and root.val > q.val: 
            return self.lowestCommonAncestor(root.left, p, q)
        return self.lowestCommonAncestor(root.right, p, q)

這樣寫的時間複雜度是 O(N)，空間複雜度也是O(N)，因為最糟的狀況是都在同一邊，要走到底才會得到結果。

參考別人的寫法後才想到可以針對 p, q 先比大小再跟 root 比，這樣會比較快，程式碼如下：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or not p or not q:
            return None
        if (max(p.val, q.val) < root.val):
            return self.lowestCommonAncestor(root.left, p, q)
        elif (min(p.val, q.val) > root.val):
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

另外也可以用迭代法，用移動指標的方式就可以處理

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if max(p.val, q.val) < root.val:
                root = root.left
            elif min(p.val, q.val) > root.val:
                root = root.right
            else:
                return root
        return None

這樣寫的時間複雜度為O(N)，空間複雜度為O(1)，因為需要用到指標的空間，不會改變。

C++的寫法跟python邏輯一樣，只有語法有調整，遞迴跟迭代的時間空間複雜度也相同。

遞迴：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// 遞迴 
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root or !p or !q){
            return NULL;
        }
        else if (max(p->val, q->val) < root->val){
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (min(p->val, q->val) > root->val){
            return lowestCommonAncestor(root->right, p, q);
        }
        else{
            return root;
        }
    }
};

// 迭代
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* ptr = root;
        while (ptr){
            if (max(p->val, q->val) < ptr->val){
                ptr = ptr->left;
            }
            else if (min(p->val, q->val) > ptr->val){
                ptr = ptr->right;
            }
            else{
                break;
            }
        }
        return ptr;
    }
};
⚠️ **GitHub.com Fallback** ⚠️