Leetcode 236. Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree

在一棵二元樹中，給定兩個節點，並找出兩個節點的最小公共祖先

Python

遞歸法 :

當這兩個節點處於不同的左右子樹中時，那麼最低公共祖先節點就是這兩棵左右子樹的根節點
當這兩個節點處於同一子樹中，那麼最低公共祖先節點就是這兩個節點中最低的那個節點

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root==p or root==q:
            return root
        left=self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)

        if left and right:
            return root
        return right if right else left

C++

1.遞歸:

定義一個遞歸函數lowestCommonAncestor(root, p, q)，用於查找p和q在以root為根節點的二叉樹中的最近公共祖先節點。

2.邊界條件：

如果當前節點root為空，或者當前節點為p或q中的一個，那麼返回當前節點。

3.遞歸處理左右子樹：

對於當前節點root，遞歸查找其左子樹和右子樹中的最近公共祖先節點。

4.判斷最近公共祖先節點：

如果左子樹中沒有找到最近公共祖先節點，那麼最近公共祖先節點在右子樹中，返回右子樹查找到的最近公共祖先節點。

如果右子樹中沒有找到最近公共祖先節點，那麼最近公共祖先節點在左子樹中，返回左子樹查找到的最近公共祖先節點。

如果左右子樹都找到了最近公共祖先節點，那麼當前節點root就是最近公共祖先節點，返回root。

時間複雜度：O(n)，其中n為二叉樹中的節點個數。每個節點最多被訪問兩次。

空間複雜度：O(n)，其中n為二叉樹中的節點個數

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

Python

C++

相關