二叉樹的最近公共祖先&&二叉搜尋樹的最近公共祖先

主要思考如下幾點：

• 如何自底向上周遊？
• 周遊整棵樹，還是周遊局部樹？
• 如何把結果傳到根結點？

關于如果遞歸函數有傳回值，如何區分是要搜尋一條邊，還是搜尋整個樹：

case1: 搜一條邊的寫法：

//若遞歸函數傳回值不為空，則立即傳回
if (遞歸函數(root->left)) return ;
if (遞歸函數(root->right)) return ;
           

case2: 搜尋整個樹的寫法：

left = 遞歸函數(root->left);
right = 遞歸函數(root->right);
left與right的邏輯處理;
           

1. 自底向上尋找，即回溯，二叉樹回溯的過程即是自底向上，而後序周遊就是天然的回溯過程。

2. 怎麼判斷一個結點是結點q和結點p的公共祖先呢：如果找到一個結點，其左子樹出現結點q

   ，右子樹出現結點p，或者反之，則，該結點即位結點p和q的最近公共祖先

3. 确定傳回值類型：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == q || root == p || root == NULL)
            return root;
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(left != NULL && right != NULL) return root;

        if(!left && right) return right;
        else if(!right && left) return left;
        else return NULL;

    }
};
           

因為二叉搜尋樹是有序的，即可以告訴我們周遊方向，故可以使用前序周遊（這裡什麼周遊都可，因為不需要進行中間結點）

這裡是遇到符合條件的結點就傳回，故符合上面第一種情況

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //if(root == NULL) return root;
        //if(root->val >= p->val && root->val <= q->val)
            //return root;
        
        if(root->val > p->val && root->val > q->val){
            TreeNode* l = lowestCommonAncestor(root->left, p, q);
            if(l) return l;
        }

        if(root->val < p->val && root->val < q->val){
            TreeNode* r = lowestCommonAncestor(root->right, p, q);
            if(r) return r;
        }

        return root; //root節點在區間（p->val <= root->val && root->val <= root->val）或者 （root->val <= cur->val && cur->val <= root->val）中
          
        
    }
};