Tarjan 's Algorithm과 하나의 알고리즘을 사용하여 웹 사이트 : http://discuss.techinterview.org/default.asp?interview.11.532716.6에서 문제를 해결하려고했지만 아무 것도 명확하지 않습니다. 어쩌면 내 재귀 개념이 제대로 구축되지 않을 수도 있습니다. 위의 두 가지 예를 설명하기 위해 작은 데모를주십시오. 유니언 찾기 데이터 구조에 대한 아이디어가 있습니다.이진 트리의 가장 낮은 공통 조상 (이진 검색 트리가 아님)
매우 흥미로운 문제입니다. 어쨌든 문제를 해독해야합니다. 면접 준비.
다른 로직/알고리즘이 있으면 공유하십시오.
LCA 알고리즘은 간단한 두 가지 작업을 시도합니다. 문제의 두 노드에서 루트까지 경로를 찾아냅니다. 이제이 두 경로는 공통 접미사를 갖습니다 (경로가 루트에서 끝나는 것으로 가정). LCA는 접미어가 시작되는 첫 번째 노드입니다. 다음과 같이
는 LCA를 찾기 위해r * /\ s * * /\ u * * t //\ * v * * /\ * *
(유, v)를 우리가 진행 :
는 다음과 같은 트리를 고려 경로 (u, r) = usr
이제, 우리는 공통의 접미사를 확인 :
참고 실제 알고리즘 까지 루트까지 올라간다. 그들은 disjoint-set 데이터 구조를 사용하여 s에 도달하면 중지합니다.
훌륭한 대체 접근법 세트가 here으로 설명되어 있습니다.
취업 면담을 언급 한 이래로 나는 O (1) 메모리 사용으로 제한되는이 문제의 변형을 생각했습니다.
1), 루트 노드 U를에서 나무를 스캔 경로 길이 L (U)
2) 노드 V에서 나무를 스캔을 찾는 :이 경우
다음 알고리즘을 고려 루트 길이까지 경로 길이 찾기 L (v)3) 경로 길이 차이 D = | L (u) -L (v) |
4) 루트
5) 동일한 노드에 충돌 할 때까지
6) 등이 노드를 돌려, 두 노드에서 동시에 트리를 걸어에서 긴 경로에서 건너 뛰기 D 노드 LCA
한 번만 (데이터 세트 당) 문제를 해결해야한다고 가정하면 간단한 접근은 한 노드에서 (자체와 함께) 조상 세트를 수집 한 다음 다른 서버에서 조상 목록을 이동할 때까지 반드시 가장 낮은 공통 조상 인 위 집합의 구성원을 찾으십시오. 이 의사 코드가 주어진다
Let A and B begin as the nodes in question.
seen := set containing the root node
while A is not root:
add A to seen
A := A's parent
while B is not in seen:
B := B's parent
B is now the lowest common ancestor.
다른 방법은 그 후, 각 노드는 전체 경로 간 공간을 계산 공통 접미사 찾고 오른쪽에서 스캔한다. 첫 번째 요소는 LCA입니다. 어느 쪽이 빠른지는 데이터에 따라 다릅니다. 당신이 노드의 여러 쌍의 LCA를 찾을 필요하게 될 경우
는, 당신은 다양한 공간/시간 절충 할 수 있습니다 : 당신은, 예를 들어, 각 노드의 깊이를 미리 계산할 수
을하는 더 깊은 노드에서 더 얕은 노드의 깊이로 먼저 걸어서 잠금 단계에서 두 노드를 루트쪽으로 걸어 갈 때마다 매번 세트 (또는 경로)를 다시 만드는 것을 피할 수 있습니다. 이러한 경로가 만나는 경우 LCA를 가져야한다.
또 다른 접근법은 깊이 - mod-H에서 다음 조상을 가진 노드에 주석을 달아서, 당신이 먼저 비슷한 문제가있는 H-times-smaller 문제와 H-sized 문제의 첫 번째 문제를 푸는 것입니다. 이것은 매우 깊은 나무에서 좋으며, H는 일반적으로 나무의 평균 깊이의 제곱근으로 선택됩니다.
허용 된 경우 더 잘 수행 할 수 있습니다 트리를 사전 처리합니다. – Ian
한 가지 덧글 : 나무는 주로 (대부분) 균형을 이룹니다. 이러한 경우 분리 된 집합 데이터 구조를 사용하는 오버 헤드는 u에서 루트까지 간단히 표시 한 다음 v에서 첫 번째로 표시된 노드에 대한 루트까지 검색하는 것보다 비용이 많이 듭니다. – Rafe