문제
아래 트리에서 트리의 높이와 노드 9의 깊이를 더한 값은?
<트리 구조>
- 루트 노드는 1이다.
- 1의 자식은 2, 3이다.
- 2의 자식은 4, 5이다.
- 3의 자식은 6, 7이다.
- 6의 자식은 9이다.
<조건>
- 트리의 높이는 루트에서 가장 깊은 단말 노드까지의 간선 수로 계산한다.
- 노드의 깊이는 루트에서 해당 노드까지의 간선 수로 계산한다.
① 6 ② 7 ③ 8 ④ 9
정답
1번
해설
정답: 1. 루트 1에서 가장 깊은 단말 노드 9까지의 경로는 1→3→6→9이므로 트리의 높이는 3이다. 노드 9의 깊이도 루트에서 9까지의 간선 수인 3이다. 따라서 합은 3+3=6이다.
오답 풀이
- 1번: 높이 3과 깊이 3을 더한 값이다.
- 2번: 높이나 깊이 중 하나를 노드 수 기준으로 계산한 값에 가깝다.
- 3번: 간선 수 대신 노드 수를 과도하게 반영한 값이다.
- 4번: 높이와 깊이를 모두 크게 계산한 값이다.
보충 개념 트리 문제에서는 높이와 깊이를 간선 수 기준으로 세는지, 노드 수 기준으로 세는지 조건을 반드시 확인해야 한다.