프로그래밍 퀴즈 – 이진 트리 – 가장 가까운 공통 조상

어떤 이진 검색 트리에 든 두 노드의 값이 주어졌을 때 가장 가까이 있는 공통 조상을 찾아내라. 두 값은 모두 분명히 그 트리 안에 있다고 가정해도 좋다.

정답

현재 노드 검사
value1과 value2가 모두 현재 노드의 값보다 작으면
   왼쪽 자식 검사
value1과 value2가 모두 현재 노드의 값보다 크면
   오른쪽 자식 검사
그렇지 않으면
   현재 노드가 가장 가까운 공통 조상

최 재훈

블로그, 페이스북, 트위터 고성능 서버 엔진, 데이터베이스, 지속적인 통합 등 다양한 주제에 관심이 많다.
Close Menu