LeetCode 235：二叉搜索樹最近公共祖先——遞歸與迭代雙解法

題目背景

給定一棵二叉搜索樹 (BST)，找到該樹中兩個指定節點的最近公共祖先 (LCA)。根據定義，最近公共祖先是指一個節點，它同時是兩節點的祖先，且深度最大（離節點最近）。

BST 性質與解題關鍵

利用 BST「左子樹 < 根 < 右子樹」的有序性質：

• 若 p、q 值均 小於 當前節點值 → LCA 在 左子樹。
• 若 p、q 值均 大於 當前節點值 → LCA 在 右子樹。
• 否則（一大一小，或等於當前節點）→ 當前節點即為 LCA。

遞歸解法

/**
 * 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) {
        if (root == null || p == null || q == null) return root;

        // 確保 p.val <= q.val 便於邏輯判斷
        if (p.val > q.val) {
            TreeNode temp = p;
            p = q;
            q = temp;
        }

        if (q.val < root.val) {
            // 兩節點均在左子樹
            return lowestCommonAncestor(root.left, p, q);
        } else if (p.val > root.val) {
            // 兩節點均在右子樹
            return lowestCommonAncestor(root.right, p, q);
        } else {
            // 分叉點或命中節點
            return root;
        }
    }
}

迭代解法（推薦，空間 O(1)）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 確保 p.val <= q.val
        if (p.val > q.val) {
            TreeNode temp = p;
            p = q;
            q = temp;
        }

        TreeNode cur = root;
        while (cur != null) {
            if (q.val < cur.val) {
                cur = cur.left;
            } else if (p.val > cur.val) {
                cur = cur.right;
            } else {
                return cur; // 找到分叉點
            }
        }
        return null; // 理論上不會執行到此
    }
}

複雜度分析

最壞情況樹退化為鏈表，h = n；平衡樹下 h = log n。

核心提示

• 利用 BST 有序性質，無需遍歷整樹。
• 迭代寫法更優雅，避免棧溢出風險。
• 注意處理 p、q 大小關係，代碼更簡潔。