235. 搜索二叉樹的最近公共祖先

思路

利用搜索二叉樹的性質，可以加快找到祖先的速度。 現在給定兩個要找到祖先的節點 $p,q$ ，且 $p\neq{q}$ ，搜索從根結點 $root$ 開始。

• 若現在結點 $\text{node}$ 的數值 $x$ 在 $p,q$ 之間，也就是 $\min(p,q)<{x}<\max(p,q)$ ， 因為搜索二叉樹的性質， $\min(p,q)$ 會在當前節點的左樹區域， $\max(p,q)$ 會在右樹， $\text{node}$ 就是祖先。
• 如果 $x<\min(p,q)<\max(p,q)$ ，所求會在 $\text{node}$ 的右樹。
• 如果 $\min(p,q)<\max(p,q)<x$ ，所求會在 $\text{node}$ 的左側。 如果在找祖先的過程中 $\text{node} = p, q$ ，就相當於上一題的情況一：其中一個節點是另一個節點的祖節點。 直接回傳 $\text{node}$ 。

程式碼

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root && root != p && root != q) { // 先判斷節點存在，再判斷是否等於 p, q
            if(min(p->val, q->val) < root->val && root->val < max(p->val, q->val)) { // 數值在兩者之間
                break;
            }
            // 能取代下面註解掉的那一段
            root = root->val < min(p->val, q->val) ? root->right : root->left;
            // if(root->val < min(p->val, q->val)) {
            //     root = root->right;
            // }
            // else if(root->val > max(p->val, q->val)) {
            //     root = root->left;
            // }
        }
        return root; 
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$