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

  • Post author:
  • Post category:칼럼
  • Post comments:0 Comments
  • Post last modified:August 25, 2014

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

정답

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

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.