劍指 Offer 68 - 二叉樹的最近公共祖先

文章目錄

• ​​劍指 Offer 68 - I. 二叉搜尋樹的最近公共祖先​​
• ​​劍指 Offer 68 - II. 二叉樹的最近公共祖先​​

劍指 Offer 68 - I. 二叉搜尋樹的最近公共祖先

在二叉搜尋樹中，公共祖先一定是從根節點往下查找的過程中，第一個值介于兩節點值之間的節點

非遞歸版

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* cur = root;
        int big = max(p->val, q->val);
        int small = min(p->val, q->val);
        
        while(!cur && (cur->val < small || cur->val > big)){
            if(cur->val < small){
                cur = cur->right;
            }else{
                cur = cur->left;
            }
        }
        return cur;
    }
};      

遞歸版

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* cur, TreeNode* p, TreeNode* q) {
        int big = max(p->val, q->val);
        int small = min(p->val, q->val);
        if(!cur || (cur->val >= small && cur->val <= big)){
            return cur;
        }

        if(cur->val < small){
            return lowestCommonAncestor(cur->right, p, q);
        }else{
            return lowestCommonAncestor(cur->left, p, q);
        }
    }
};      

劍指 Offer 68 - II. 二叉樹的最近公共祖先

祖先的定義： 若節點 p 在節點 root 的左（右）子樹中，或 p = root ，則稱 root 是 p 的祖先

最近公共祖先的定義： 設節點 root 為節點 p,q 的某公共祖先，若其左子節點 root.left 和右子節點 root.right 都不是 p,q 的公共祖先，則稱 root 是 “最近的公共祖先”

根據以上定義，若 root 是 p,q 的 最近公共祖先 ，則隻可能為以下情況之一：

1. p 和 q 在 root 的子樹中，且分列 root 的 異側（即分别在左、右子樹中）；
2. p=root ，且 q 在 root 的左或右子樹中；
3. q=root ，且 p 在 root 的左或右子樹中；

考慮通過遞歸對二叉樹進行先序周遊，當遇到節點 p 或 q 時傳回。從底至頂回溯，當節點 p,q 在節點 root 的異側時，節點 root 即為最近公共祖先，則向上傳回 root

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(nullptr == root || root == p || root == q){
            return root;
        }

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(nullptr != left && nullptr != right){
            // p q在root的兩側，則root為最近公共祖先
            return root;
        }
        return nullptr == left ? right : left;
    }
};