콘텐츠로 이동

7.7   연습 문제

7.7.1   개념 확인

1.   완전 이진 트리, 정 이진 트리, 포화 이진 트리

다음 두 배열은 이진 트리를 레벨 순서로 나타낸 것이다. None은 빈자리를 뜻한다.

  • 트리 A: [1, 2, 3, 4, 5, 6]
  • 트리 B: [1, 2, 3, None, None, 6, 7]
  1. 어느 트리가 완전 이진 트리인가?
  2. 어느 트리가 모든 비리프 노드에 자식이 두 개씩 있는 정 이진 트리인가?
  3. 두 트리 중 포화 이진 트리가 있는가? 각각 이유를 설명하라.
참고 답안

  1. 트리 A는 완전 이진 트리다. 맨 아래 레벨만 가득 차지 않았고, 노드가 왼쪽부터 연속해서 배치되어 있다. 트리 B는 맨 아래 레벨의 왼쪽에 빈자리가 있는데 오른쪽에 노드가 있으므로 완전 이진 트리가 아니다.

  2. 트리 B는 정 이진 트리다. 노드 1과 노드 3은 자식이 각각 두 개이고, 나머지는 모두 리프 노드다. 트리 A의 노드 3에는 왼쪽 자식 6만 있으므로 정 이진 트리가 아니다.

  3. 두 트리 모두 맨 아래 레벨이 완전히 채워져 있지 않으므로 포화 이진 트리가 아니다.

2.   같은 트리의 세 가지 순회 순서

배열 [1, 2, 3, 4, 5, 6, 7]을 레벨 순서로 완전 이진 트리에 저장한다.

  1. 이 트리를 그려 보자.
  2. 전위, 중위, 후위 순회 결과를 각각 적어 보자.
  3. 중위 순회 결과에서 루트 노드 1의 왼쪽과 오른쪽에 있는 두 수열은 각각 트리의 어느 부분에 대응하는가?
참고 답안

  1. 트리는 다음과 같다.

          1
    /   \
   2     3
  / \   / \
 4   5 6   7

  2. 전위 순회는 1, 2, 4, 5, 3, 6, 7이다. 중위 순회는 4, 2, 5, 1, 6, 3, 7이다. 후위 순회는 4, 5, 2, 6, 7, 3, 1이다.

  3. 루트 노드 1의 왼쪽에 있는 4, 2, 5는 왼쪽 서브트리의 중위 순회 결과다. 오른쪽의 6, 3, 7은 오른쪽 서브트리의 중위 순회 결과다.

3.   두 이진 탐색 트리 비교하기

다음 두 수열을 각각 왼쪽부터 빈 이진 탐색 트리에 차례대로 삽입한다.

  • 수열 A: [4, 2, 6, 1, 3, 5, 7]
  • 수열 B: [1, 2, 3, 4, 5, 6, 7]
  1. 숫자 7을 찾을 때 거치는 노드를 각각 적어 보자.
  2. 높이를 루트에서 가장 먼 리프까지 지나는 간선 수로 계산할 때, 두 트리의 높이는 각각 얼마인가?
  3. 앞선 두 질문을 바탕으로 두 트리에서 7을 찾는 효율성이 같은지 판단하라. 트리의 모양과 탐색 경로를 바탕으로 이유를 설명하라.
참고 답안

  1. 수열 A로 만든 트리의 탐색 경로는 4 → 6 → 7이다. 수열 B로 만든 트리의 탐색 경로는 1 → 2 → 3 → 4 → 5 → 6 → 7이다.

  2. 첫 번째 트리는 모든 레벨이 가득 차 있고 높이는 2다. 두 번째 트리는 오른쪽 자식만 있으며 높이는 6이다.

  3. 두 트리에서 7을 찾는 효율성은 다르다. 삽입 순서가 이진 탐색 트리의 모양과 높이를 바꾸기 때문이다. 첫 번째 트리는 노드 3개만 거치지만, 두 번째 트리는 노드 7개를 차례대로 거친다. 트리가 높을수록 최악의 경우 경로를 따라 비교해야 하는 노드가 많아진다.

7.7.2   프로그래밍 연습

1.   이진 트리의 최대 깊이

이진 트리의 루트 노드 root가 주어진다. 각 노드는 정숫값과 왼쪽 및 오른쪽 자식 노드에 대한 참조를 가진다.

루트에서 가장 먼 리프까지 거치는 노드 수를 이진 트리의 최대 깊이라고 정의한다. 이 트리의 최대 깊이를 반환하라. 빈 트리의 최대 깊이는 0이다. 재귀를 사용하여 해결하라.

풀이 힌트
  1. 이 문제에서는 노드 수로 깊이를 계산한다. 루트 하나만 있는 트리의 최대 깊이는 1이다.
  2. 재귀 함수가 현재 노드를 루트로 하는 서브트리의 최대 깊이를 반환하도록 한다.
  3. 빈 노드는 0을 반환하고, 비어 있지 않은 노드는 max(depth(left), depth(right)) + 1을 반환한다.

LeetCode

2.   이진 트리를 레벨 순서로 순회하기

이진 트리의 루트 노드 root가 주어진다. 큐를 사용하여 위에서 아래로 한 레벨씩 모든 노드를 방문하라. 같은 레벨에서는 왼쪽부터 오른쪽으로 방문한다.

2차원 배열을 반환하라. 첫 번째 하위 배열에는 루트가 있는 레벨의 노드 값을, 두 번째에는 다음 레벨의 노드 값을 저장하며 이 방식을 반복한다. 빈 트리라면 빈 배열을 반환하라.

풀이 힌트
  1. 레벨 순서 순회에서는 먼저 들어온 노드를 먼저 방문해야 하므로 큐를 사용한다.
  2. 각 반복이 시작될 때 큐에 있는 노드들은 정확히 같은 레벨에 속한다.
  3. 큐의 길이를 먼저 기록한 뒤 그 수만큼 노드를 꺼내고 각 노드의 자식을 넣는다.

LeetCode

3.   이진 탐색 트리에서 k번째로 작은 원소

이진 탐색 트리에 총 n개의 노드가 있으며, 노드 값은 모두 다르다. 모든 노드 값을 작은 것부터 나열하고 위치에 1부터 번호를 붙인다.

루트 노드 root와 1 <= k <= n을 만족하는 정수 k가 주어질 때, k번째 노드 값을 반환하라. 모든 값을 미리 모으지 말고 중위 순회 도중에 바로 답을 찾아라.

풀이 힌트
  1. 이진 탐색 트리를 중위 순회하면 노드 값을 작은 것부터 방문한다.
  2. 중위 순회는 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순서로 처리한다. 현재 노드를 방문할 때 개수를 1 늘린다.
  3. 개수가 처음 k가 되었을 때의 노드 값이 답이다. 이후에는 순회를 계속할 필요가 없다.

LeetCode

댓글로 의견이나 질문, 제안을 남겨 주세요