Daniel's blog

이진 트리 또는 이진 검색 트리(BST)에서 두 노드의 최하 공통 조상(LCA)를 찾는 데는 몇 가지 일반적인 접근 방식이 있다. 가장 좋은 방법은 트리이 특정 특성(BST 인지, 균형이 잡혀있는지(balanced) 등)과 추가 정보 (각 노드의 조상 또는 트리의 전처리 기능 등)에 따라 달라진다. 아래는 몇 가지 일반적인 방법이다. Single Traveral Method (단일 순회 방법, 재귀 사용) : 이 방법은 추가 정보가 제공되지 않는 트리에서 LCA를 찾는 데 널리 사용되는 방법이다. 아이디어 : 루트에서 시작해 트리를 순회한다. 각 노드에 대해 현재 노드가 LCA를 찾고자 하는 두 노드 중 하나인지 확인한다. 맞다면 현재 노드를 반환한다. 그렇지 않으면 왼쪽 및 오른쪽 자식에 대해 재귀 호..

GeeksforGeeks에 따르면 Lowest Common Ancestor(LCA)의 정의는 아래와 같다. : The lowest common ancestor is the lowest node in the tree that has both n1 and n2 as descendants, where n1 and n2 are the nodes for which we wish to find the LCA. Hence, the LCA of a binary tree with nodes n1 and n2 is the shared ancestor of n1 and n2 that is located farthest from the root. : LCA는 트리에서 n1과 n2를 자손(descendants)으로 가지는 가장..