[Programmers] 트리 트리오 중간값

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/68937

코딩테스트 연습 - 트리 트리오 중간값

트리의 지름을 구하는 문제를 응용하는 문제였습니다.

(https://jaimemin.tistory.com/812)

 

알고리즘은 아래와 같습니다.

1. 1번 노드를 기준으로 제일 멀리 있는 노드를 찾습니다.

2. 1번에서 구한 노드를 기준으로 제일 멀리 있는 노드를 찾습니다 즉, 트리의 지름을 찾습니다.

2.1 제일 멀리 있는 노드들이 여러 개일 경우 중간값이 트리의 지름이므로 트리의 지름을 반환해줍니다.

3. 2번에서 구한 노드 개수가 하나일 경우 한번 더 트리의 지름을 구해서 가장 멀리 있는 노드가 여러 개인지 확인해줘야 합니다.

3.1 여러 개이면 2.1번과 마찬가지로 트리의 지름을 반환해줍니다.

3.2 하나라면 [트리의 지름, 트리의 지름 - 1,..]와 같은 형식이므로 트리의 지름 - 1을 반환해줍니다.

 

더 자세한 내용은 아래 블로그를 참고해주세요.

https://jinee0717.tistory.com/57

[Algorithm] 프로그래머스 트리 트리오 중간값 - 트리의 지름

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~