[알고리즘] LCA(Lowest Common Ancestor) 최소공통조상

Binary Tree에서 최소공통조상 LCA를 찾는 로직. 

직접 Tree와 스택을 종이에 써보면서 따라가보면 이해가 쉽다.

 

Leetcode 236. Lowest Common Ancestor of a Binary Tree

Input/Output

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.

 

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return None
        # if p, q is root, return root
        if p == root or q == root:
            return root
        # else look in left and right child
        left_la = self.lowestCommonAncestor(root.left, p, q)
        right_la = self.lowestCommonAncestor(root.right, p, q)
        
        # either one of the chidren returned a node, meaning either p or q found on left or right branch.
        # Example: assuming 'p' found in left child, right child returned 'None'. This means 'q' is
        # somewhere below node where 'p' was found we dont need to search all the way, 
        # because in such scenarios, node where 'p' found is LCA
        if left_la and not right_la:
            return left_la
        if right_la and not left_la:
            return right_la
            
        # if you found p, q from both left/right, that's the LCA.
        # you can remove the if statement here as well
        if left_la and right_la:
            return root

 

응용 문제

2096. Step-By-Step Directions From a Binary Tree Node to Another