이진 트리 비 재귀 버전에서 최소한의 공통 조상 검색 - Java

Question

Java에서 작성한 정렬 된 이진 트리에서 가장 공통적 인 조상을 찾는 재귀적인 알고리즘이 아닌 버전을 검색하고 있습니다. 내가 발견 한 모든 것은 Stackoverflow 및 다른 웹 사이트의 재귀 버전입니다.

while 회 돌이를 사용하여 비 재귀 버전을 쓰거나 지시 할 수 있습니까? 이 버전이 시간 복잡성 측면에서 더 효율적인 경우 작성 하시겠습니까?

Answer 1

이 오랫동안 잊혀진 질문을 만났습니다. 그런

 A 
    B  C 
D E F G 
H I J K L M N O 

commonAncestor(L,G) = C 
commonAncestor(H,O) = A 
commonAncestor(B,H) = B 

무엇인가 : 당신이 나무를 부여하는 경우

당신은 같은 것을 의미합니까?

이 방법은 (모든 트리에 제공된 노드를 가정)을 얻었다 : 부모에 대한 링크가있는 경우 (즉, 다시 A와 B에서 가리키고있다), 다음 솔루션은 발견 유사 쉽게

연결된 목록을 교차 :

깊이가 D1 및 D2이라고 가정 할 때 Node1과 Node2의 깊이를 찾습니다. D1과 D2 (d으로 가정)의 차이점을 찾으십시오. Node1과 Node2에 대한 포인터가 있어야합니다 (p1과 p2로 가정). 깊이가 더 높은 노드의 경우 상위 d 번째 시간으로 이동합니다. 이 시점에서 p1 및 p2은 조상 아래에 동일한 깊이를 갖습니다. 노드가 p1 == p2이 될 때까지 p1과 p2을 부모 노드로 이동하는 간단한 루프 만 있습니다.

---

노드에서 부모의 링크를 클릭하거나 반복적으로 트리 탐색 할 수없는 경우

currentNode = root; 
while (true) { 
    if ((currentNode > node1 && currentNode < node2) || 
     (currentNode < node1 && currentNode > node2)) { 
     break; // current node is the common ancestor, as node1 and node2 
       // will go to different sub-tree 
    } else if (currentNode > node1) { 
     currentNode = currentNode.left; 
    } else { // currentNode < node1/2 
     currentNode = currentNode.right; 
    } 
} 

// currentNode will be the answer you want 

을