Lowest Common Ancestor1 Lowest Common Ancestor of a Binary Tree 최소 공통 조상 알고리즘 [LeetCode 236] 최소 공통 조상 이진 트리(Binary Tree)에서 최소 공통 조상(Lowest Common Ancestor)이란, 서로 다른 두 노드의 조상 노드 집합을 각각 A와 B라고 할 때, 교집합(A n B)에 속하는 원소 중 가장 하위에 존재하는 노드를 의미합니다. 여기서 조상 노드 집합이라는 개념은, 본 노드를 포함하는 개념임을 주의해야 합니다. 예를 들어서 A 노드의 조상 노드 집합에는, A노드보다 상위에 직 / 간접적으로 연결되어 있는 노드 뿐 아니라, A 노드도 포함이 됩니다. 위 이진 트리(Binary Tree)에서 A노드와 B노드의 최소 공통 조상을 찾아보겠습니다. A와 B의 공통 조상은 핑크색으로 표시해 두었습니다. 이 핑크색으로 표시된 노드 중 가장 하위에 존재하는 노드인 5가 바로 A와 B의.. 2024. 4. 1. 이전 1 다음
