圖論經典: 二元樹中的最接近公共祖先節點 LCA of a Binary_Leetcode #236 精選75題

Carlos Soria on Unsplash

題目敘述

題目會給定一顆二元樹的根結點Root node，和這棵樹中的任意兩個節點p, q。

請找出p, q 在這棵二元數裡面的最接近公共祖先節點是誰?

最接近的公共節點: 就是p, q兩個節點從下往上走，第一個交會的節點。

題目的原文敘述

測試範例

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

節點5和節點1的公最接近公共節點是 節點3

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
節點5和節點4的公最接近公共節點是 節點5

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1
節點1和節點2的公最接近公共節點是 節點1

演算法 討論可能的情況，並且分類。使用DFS深度優先搜索

假如從樹根Root node開始往下搜索的話，會有下列幾種情況。

1. 空節點、或 空樹，一定不可能是別人的共同祖先，返回None。
2. 現在這個節點剛好是p 或者 剛好是q，返回當下這個節點。
3. p, q 都落在右子樹(root.right)裡面，遞回去右子樹裡面找。
4. p, q 都落在左子樹(root.left)裡面，遞回去左子樹裡面找。
5. p, q 剛好其中一個在左子樹裡面，另一個在右子樹裡面，那麼，當下的root node剛好就是最接近公共祖先節點。

最接近的公共節點: 就是p, q兩個節點從下往上走，第一個交會的節點。

程式碼 討論可能的情況，並且分類。使用DFS深度優先搜索

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        if not root:
            # Empty tree or empty node
            return None

        if root is p or root is q:
            # Current node is either p or q
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if not left:
            # Both p, q reside in right subtree
            return right
        elif not right:
            # Both p, q reside in left subtree
            return left
        else:
            # One reside in left subtree, the other reside in right subtree
            # Current root node is Lowest Common Ancestor of (p, q)
            return root

複雜度分析 討論可能的情況，並且分類。使用DFS深度優先搜索

時間複雜度:

從根結點開始，探索整顆樹，每個結點最多拜訪一次，所需時間為O(n)。

空間複雜度:

從根結點開始，探索整顆樹，遞迴深度最深為n，發生在整顆樹向左歪斜或向右歪斜的時候，所需recursion call stack最深為O(n)。