235. Lowest Common Ancestor of a Binary Search Tree

題目網址：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

題意：給一 BT 和兩個節點 p, q, 求兩節點之最低共同祖先(LCA)

Solution：

想法：利用 DFS 和 BST 的性質, 找到一 node 滿足 node.val 介於 p、q 之間

• p->val ≤ node.val ≤ q->val 或
• q->val ≤ node.val ≤ p->val

BST 性質:

• root 左子樹中所有 node.val 皆小於 root.val
• root 右子樹中所有 node.val 皆大於 root.val

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val > root->val && q->val > root->val) { // 當前 root 太小
            return lowestCommonAncestor(root->right, p, q);
        } else if (p->val < root->val && q->val < root->val) { // 當前 root 太大
            return lowestCommonAncestor(root->left, p, q);
        }
        return root; // 當前 root->val 介於 p、q 之間, 故返回 root
    }
};

• time：$O(n)$ ➔ skew tree, 遍歷整個 BT
• space：$O(n)$ ➔ skew tree, 遞迴深度為 n