LeetCode 235：二叉搜索樹的最近公共祖先 — 利用 BST 性質遞歸/迭代

題目描述

給定一個二叉搜索樹 (BST) 及兩個節點 p、q，找到它們的最近公共祖先 (LCA)。LCA 定義允許節點是自身的後代。

BST 性質回顧： 左子樹所有節點值 < 根節點值 < 右子樹所有節點值。

解題思路

從根節點開始：

• 若 p.val < root.val 且 q.val < root.val，LCA 在左子樹，遞歸左子樹。
• 若 p.val > root.val 且 q.val > root.val，LCA 在右子樹，遞歸右子樹。
• 否則（一大一小，或其中一個等於根），當前根即為 LCA。

遞歸與迭代均可，迭代更省空間。

參考代碼 (C++)

/**
 * 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) {
        // 迭代版
        while (root) {
            if (p->val < root->val && q->val < root->val)
                root = root->left;
            else if (p->val > root->val && q->val > root->val)
                root = root->right;
            else
                return root;
        }
        return nullptr; // 理論上不會到達
    }
};

複雜度分析

• 時間複雜度：O(h)，h 為樹高（平均 O(log n)，最壞 O(n)）。
• 空間複雜度：O(1) 迭代，O(h) 遞歸。