[Algorithm] Lowest Common Ancestor (LCA)

이진 트리 또는 이진 검색 트리(BST)에서 두 노드의 최하 공통 조상(LCA)를 찾는 데는 몇 가지 일반적인 접근 방식이 있다. 가장 좋은 방법은 트리이 특정 특성(BST 인지, 균형이 잡혀있는지(balanced) 등)과 추가 정보 (각 노드의 조상 또는 트리의 전처리 기능 등)에 따라 달라진다. 아래는 몇 가지 일반적인 방법이다.

 

1. Single Traveral Method (단일 순회 방법, 재귀 사용)
   : 이 방법은 추가 정보가 제공되지 않는 트리에서 LCA를 찾는 데 널리 사용되는 방법이다.
   
   1. 아이디어
      : 루트에서 시작해 트리를 순회한다. 각 노드에 대해 현재 노드가 LCA를 찾고자 하는 두 노드 중 하나인지 확인한다. 맞다면 현재 노드를 반환한다. 그렇지 않으면 왼쪽 및 오른쪽 자식에 대해 재귀 호출을 한다.
   2. 작동 방식
      : 두 재귀 호출 모두 null이 아닌 값을 반환하면 현재 노드가 LCA라는 뜻이다(한 노드는 왼쪽 하위 트리에서, 다른 노드는 오른쪽 하위 트리에서 발견되기 때문). 재귀 호출 중 하나만 null이 아닌 값을 반환하면 두 노드가 모두 해당 하위 트리에 있으며 null이 아닌 반환 값이 LCA라는 의미다.
   3. 효율성
      : 이 방법은 트리를 한 번만 탐색하므로 O (n) 시간 내에 작동한다.
2. 경로 비교 방법
   : 이진 트리에서 LCA를 찾는 또 다른 접근 방식은 두 단계로 이뤄진다. 이 방법도 O (n) 시간이 걸리지만 경로를 저장하는 데 트리의 높이만큰 공간이 필요해, 단일 순회 방법보다 공간 복잡도 측면에서 효율성이 떨어진다.
   1. 단계
      : 루트에서 주어진 두 노드까지의 경로를 찾아 두 개의 목록에 저장한다.
   2. 단계
      : 경로의 값이 같을 때까지 두 경로를 모두 순회한다. 마지막 공통 노드는 LCA다.
3. 부모 포인터 사용
   : 각 노드에 부모 노드에 대한 포인터가 포함되어 있으면 다른 전략으로 LCA를 찾을 수 있다.
   1. 아이디어
      : 한 노드에서 루트까지 순회해 방문한 상위 노드를 표시한다. 그런 다음 표시된 상위 노드에 도달할 때까지 다른 노드에서 위로 이동한다.
   2. 작동 방식
      : 두 번째 순회 중에 처음 만나는 표시된 조상이 LCA다.
   3. 효율성
      : 이 방법은 모든 노드의 부모 노드에 빠르게 접근할 수 있는 경우 더 효율적일 수 있으며, O (h) 시간 복잡도와 공간 복잡도를 갖는다. (h는 트리의 높이)
4. 이진 검색 트리 속성
   : 트리가 이진 검색 트리의 경우, BST의 속성을 사용해 보다 효율적으로 LCA를 찾을 수 있다.
   1. 아이디어
      : 루트에서 시작해 BST 속성에 따라 두 노드의 경로를 분할한다(왼쪽 자식은 모두 현재 노드보다 작고, 오른쪽 자식은 모두 현재 노드보다 큼).
   2. 작동 방식
      : 두 노드의 경우 한 값이 루트보다 작고 다른 값이 크면 루트가 LCA가 된다. 둘 다 작거나 둘 다 크면 각각 왼쪽 또는 오른쪽 자식으로 이동한다.
   3. 효율성
      : 이 방법은 루트에서 트리의 깊이까지 최대 한 번만 이동하기 때문에 O (h) 시간 복잡도로 작동한다. (h는 역시 트리의 높이)
5. Directed Acyclic Graphs (DAGs, 방향성 비순환 그래프)
   : DAG 또는 더 복잡한 구조의 트리에서 LCA를 찾는 것과 같이 더 복잡한 경우에는 오일러 투어 트리(Euler Tour Trees), 중등도 분해(Heavy-Light Decomposition) 또는 타잔의 오프라인 LCA 알고리즘(Tarjan's Offline LCA algorithm)과 같은 고급 데이터 구조가 사용될 수 있다. 이러한 방법은 트리를 효율적으로 사전 처리해 LCA 쿼리에 빠르게 응답할 수 있다.

'2. 경로 비교 방법'을 Python으로 구현한 코드다.

class Solution:
    def helper(self, target, node, trace):
        if not node:
            return None
        # No need to print in the final solution, but left here for debugging
        # print("helper:", node.val, trace)
        trace.append(node)  # Add current node to the trace
        if node == target:
            return trace.copy()  # Return a copy of the trace up to the target
        left_result = self.helper(target, node.left, trace)
        if left_result:
            return left_result
        right_result = self.helper(target, node.right, trace)
        if right_result:
            return right_result
        trace.pop()  # Remove current node from trace if not in path to target
        return None

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        pList = self.helper(p, root, [])
        qList = self.helper(q, root, [])
        i = 0
        # Find the last common ancestor in the paths
        while i < len(pList) and i < len(qList) and pList[i] == qList[i]:
            i += 1
        return pList[i-1]  # The last common ancestor