題目：
給定一棵二元搜尋樹 (BST)，和樹中的兩個節點 p 和 q，請找出這兩個節點的最近共同祖先 (Lowest Common Ancestor, LCA)。

根據BST的性質，父節點的值大於左子節點且小於右子節點。

範例：
範例 1:

輸入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
      6
     / \
    2   8
   / \ / \
  0  4 7  9
    / \
   3   5
輸出：6
解釋：節點 2 和節點 8 的最近共同祖先是 6。

範例 2:

輸入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
      6
     / \
    2   8
   / \ / \
  0  4 7  9
    / \
   3   5
輸出：2
解釋：節點 2 和節點 4 的最近共同祖先是 2，因為根據定義，最近共同祖先可以是節點本身。

提示：

• 給定的樹是 BST。
• 所有節點的值唯一。
• p 和 q 的值保證在 BST 中都存在。

解題思路

對於 p 和 q 與當前節點有三種情況，

• 如果 p 和 q 的值都小於當前節點，表示它們都在當前節點的左子樹，所以應該往左走。
• 如果 p 和 q 的值都大於當前節點，則表示它們都在右子樹，因此應該往右走。
• 如果一個節點的值介於 p 和 q 之間，或者與其中之一相等，那麼當前節點就是它們的最近共同祖先。

遞迴版本

實作：

/**
 * 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 (p->val < root->val && q->val < root->val) { // left
            // 如果 p 和 q 的值都小於當前節點，往左子樹繼續尋找
            return lowestCommonAncestor(root->left, p, q);
        } else if (p->val > root->val && q->val > root->val) { // right
            // 如果 p 和 q 的值都大於當前節點，往右子樹繼續尋找
            return lowestCommonAncestor(root->right, p, q);
        } else { // p->val <= root->val && q->val => root->val
            // 找到最近共同祖先
            return root;
        }
    }
};

在這邊不會遍歷到 nullptr 節點。

迭代版本

實作：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root != nullptr) {
            if (p->val < root->val && q->val < root->val) { // left
                // 如果 p 和 q 的值都小於當前節點，往左子樹繼續尋找
                root = root->left;
            } else if (p->val > root->val && q->val > root->val) { // right
                // 如果 p 和 q 的值都大於當前節點，往右子樹繼續尋找
                root = root->right;
            } else { // p->val <= root->val && q->val => root->val
                // 找到最近共同祖先
                return root;
            }
        }
        return nullptr;
    }
};

小筆記：

• 這題難在怎麼想到這個方法，如果樹的遍歷方式還熟悉的話，實作是蠻簡單的。
• BST特性：所有節點的值都是唯一不重複，父節點的值大於左子節點且小於右子節點。

參考：
#235. Lowest Common Ancestor of a BST