[Algorithm] Lowest Common Ancestor (LCA)

이진 트리 또는 이진 검색 트리(BST)에서 두 노드의 최하 공통 조상(LCA)를 찾는 데는 몇 가지 일반적인 접근 방식이 있다. 가장 좋은 방법은 트리이 특정 특성(BST 인지, 균형이 잡혀있는지(balanced) 등)과 추가 정보 (각 노드의 조상 또는 트리의 전처리 기능 등)에 따라 달라진다. 아래는 몇 가지 일반적인 방법이다. Single Traveral Method (단일 순회 방법, 재귀 사용) : 이 방법은 추가 정보가 제공되지 않는 트리에서 LCA를 찾는 데 널리 사용되는 방법이다. 아이디어 : 루트에서 시작해 트리를 순회한다. 각 노드에 대해 현재 노드가 LCA를 찾고자 하는 두 노드 중 하나인지 확인한다. 맞다면 현재 노드를 반환한다. 그렇지 않으면 왼쪽 및 오른쪽 자식에 대해 재귀 호..
기술(Tech, IT)/알고리즘(Algorithm) 2024. 3. 30. 08:12
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/04   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
글 보관함
반응형