當前位置:網站首頁>二叉樹的最近公共祖先

二叉樹的最近公共祖先

2022-05-14 07:16:24Mag1calz

在這裏插入圖片描述

  • 假設我們需要找到結點p,q的最近公共祖先,我們可以發現二叉樹的最近公共祖先滿足:此結點的左結點和右節點分別存在p,q或者此節點恰好是p,q之一並且他的左右結點之一恰好是另一結點。
  • 我們假設fleft==true錶示左節點或左節點的子節點中存在其中一個元素,fleft == false則錶示左節點或左節點的子節點中不存在元素,fright同理,則判斷一個結點是否最近公共祖先結點的判斷條件是:

( f l e f t (fleft (fleft&& f r i g h t ) ∣ ∣ ( ( x = p ) ∣ ∣ ( x = q ) fright)||((x=p)||(x=q) fright)((x=p)(x=q)&& ( f l e f t ∣ ∣ f r i g h t ) ) (fleft||fright)) (fleftfright))

  • 第一個條件就是說這個結點滿足左右節點分別存在p,q。第二個條件就是說滿足此節點其中之一滿足等於兩個結點之一並且他的子節點包含另一個結點。
  • 並且我們是自底向上從葉子節點開始更新的,所以在所有滿足條件的公共祖先中一定是深度最大的祖先先被訪問到
  • 只要某個結點他的左右子結點之一滿足等於p或q,我們就將此結點的bool值定比特true。
TreeNode* ans;
bool dfs(TreeNode* root,TreeNode* p,TreeNode *q){
    
    if(root==nullptr) return false;
    bool fleft=dfs(root->left,p,q); //判斷fleft
    bool fright=dfs(root->right,p,q);
    if((fleft&&fright)||((root->val==q->val||(root->val==p->val))&&(fleft||fright))) ans=root;
    return fleft||fright||(root->val==q->val||(root->val==p->val)); //滿足其一就返回true
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
    dfs(root,p,q);
    return ans;
}

也可以用以下方法計算二叉樹的最近公共祖先:

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

        TreeNode* l = lowestCommonAncestor(root->left, p, q);
        TreeNode* r = lowestCommonAncestor(root->right, p, q);
    
        return l == nullptr ? r : (r == nullptr ? l : root);
    }

版權聲明
本文為[Mag1calz]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/134/202205140609163247.html

隨機推薦