루트가 있는 트리는 컴퓨터 과학이나 엔지니어링에서 잘 알려진 자료구조이다.

예를 들면 다음과 같다.

위 그림에서 각각의 노드는 {1,2,...,16}의 라벨을 1개씩 가지고 있다. 8번 노드는 루트이다.

만약 노드 x가 루트에서부터 노드 y까지의 경로(path) 상에 나타나면 x는 노드 y의 조상이 된다.

이를 테면 노드 4는 노드 16의 조상이다. 노드 10 역시 노드 16의 조상이다.

노드 x가 서로 다른 노드 y와 z의 조상이면 x를 y와 z의 공통 조상이라고 부른다.

이러한 공통 조상들 중에 y와 z에 가장 가까운 공통 조상을 가장 가까운 공통 조상이라고 칭한다.

따라서 2와 3의 가장 가까운 공통 조상은 10이 된다. 만약 y가 z의 조상이라면 y가 가장 가까운 공통 조상이 된다.

트리 내에서 두 개의 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하라.

가장 가까운 공통조상 찾기 timer 1s memory 64MB

가장 가까운 공통조상 찾기 1s 64MB