최저 공통 조상 (LCM) 포함하는 루트 노드

Question

나는 아래 이진 검색 트리를 가정하면, 다음의 LCM은 무엇

 30 
     /\ 
    /\ 
    8 52 
    /\ 
/\ 
    3 20 
     /\ 
    /\ 
    10 29 

:

• (30)와 8
• 20 29

나는 코드를 원하지 않지만 prob를 해결하는 방법을 생각해 낼 수 있기를 바랍니다. 흠.

Answer 1

이것은 검색 트리이므로 매우 쉽게되지만 요청에 너무 많은 세부 정보를 제공하지 않습니다.

1) 루트를 확인하십시오. 두 숫자 중 하나라면 공통 조상을 찾았습니다.

2) 검색 트리이므로 주어진 하위 트리를 신속하게 결정할 수 있습니다. (a) 왼쪽 하위 트리에있는 경우, (b) 오른쪽 하위 트리에있는 경우, (c) 왼쪽에 하나, 오른쪽에 하나를 수행해야합니다.

행운을 빈다.

Answer 2

트리의 두 노드 v와 w의 가장 낮은 공통 조상 (LCA)은 자손으로 v와 w를 모두 갖는 가장 낮은 (즉, 가장 깊은) 노드입니다. 여기서 각 노드는 자체의 자손으로 정의됩니다 v가 w와 직접 연결되어있는 경우 w는 가장 낮은 공통 조상입니다.

여기 30은 30과 8의 LCM입니다. 20은 20과 29의 LCM입니다. 20과 52의 LCM은 하위 노드로 20과 52를 모두 갖는 최하위 노드이므로 30입니다.

최소 공통 조상 두 조건을 만족 트리 유일한 노드로 정의 될 수

Answer 3

: 모든 대상 노드가이 노드 또는이 노드의 decendent 및 B. 어느이다

A. 아니요 이 노드의 자식은 조건 A를 만족합니다.

따라서 노드에 조건 A가 있지만 자식은 없다는 노드를 찾고 있습니다. 루트 노드가 조건 A를 만족한다는 것을 알 수 있습니다 (정의에 따라). 이 노드가 대상 목록에있는 경우 다음이

그렇지 않으면 어떤 만족, 시작을 A 조건

을 만족 노드의 아이를 검색 LCA는

1. : 그래서 알고리즘은 루트에서 시작하여, 다음과 같은 다시 그 아이
2. 에 대한 1 단계에서 아무도 당신이 당신의 가장 낮은 공통 조상

이 알고리즘은 단지 2 귀하의 질문에 같은 목표의 수에 대한 작동이 후 만족하지 않는 경우.

나는 코드를 원하지 않는다는 것을 알고 있지만, 자바 8 스트림을 사용하여 살펴보기를 권한다. 조건을 충족시키기 위해 아이들을 반복하는 상황에서 매우 우아하다.