在二元搜尋樹中，有這麼一個經典的題目：尋找兩節點的共同祖先！

但是共同祖先可以有很多個，所以我們會選擇最接近的共同祖先作為這題的輸出。

那要怎麼實作呢？

1. 我們先宣告函式：BSTNode *BST::lowestCommonAncestor(BSTNode *root, BSTNode *tg1, BSTNode *tg2);
   • tg1, tg2 分別代表這兩個樹節點
   • 使用遞迴搜尋最低共同祖先，所以傳入 root
2. 我們要先了解到二元搜尋樹的規則：右子節點資料 > 根節點資料 且 左子節點資料 < 根節點資料
3. 接著我們就從樹根開始判斷，大概會分成三個情況(我們稱 cur 為當前節點)
   1. cur -> data > tg1 -> data && cur -> data > tg2 -> data
      • cur 的左子樹中存在 tg1, tg2 的共同祖先
   2. cur -> data < tg1 -> data && cur -> data < tg2 -> data
      • cur 的右子樹中存在 tg1, tg2 的共同祖先
   3. tg2 -> data > cur -> data > tg1 -> data or tg2 -> data < cur -> data < tg1 -> data
      • cur 為 tg1, tg2 的 lowestCommonAncestor
   4. tg1 == cur or tg2 == cur:
      • lowestCommonAncestor 為 cur

定義 BSTNode *BST::LCA()

註：LCA 為 Lowest Common Ancestor 的縮寫

BSTNode* BST::LCA(BSTNode *root, BSTNode *tg1, BSTNode *tg2) {
        if (root == NULL) return NULL;
        if (tg1 == root || tg2 == root) 
            return root;
        if ((root -> data > tg1 -> data && root -> data < tg2 -> data) || (root -> data < tg1 -> data && root -> data > tg2 -> data)) 
            return root;
        else if (root -> data > tg1 -> data && root -> data > tg2 -> data) 
            return lowestCommonAncestor(root -> left, tg1, tg2);
        else 
            return lowestCommonAncestor(root -> right, tg1, tg2);
}

不覺得遞迴很方便嗎？

但是前提是我們必須找出規則、理清頭緒。