<aside> 💬 lv1, 데이터 구조

이진 트리의 최대 깊이 찾기

문제 설명

주어진 이진 트리의 최대 깊이(또는 높이)를 찾는 함수를 작성해주세요. 이진 트리는 리스트로 표현되며, 각 요소는 트리 노드의 값을 나타냅니다. 루트 노드는 리스트의 첫 번째 요소이며, 각 노드의 왼쪽 자식과 오른쪽 자식은 2n+1과 2n+2 위치의 요소로 표현됩니다 (n은 부모 노드의 인덱스). 빈 노드는 None으로 표현됩니다.

예를 들어, 아래와 같은 이진 트리는 [1, 2, 3, None, None, 4, 5]로 표현됩니다.

    1
   / \\\\
  2   3
       / \\\\
     4   5

제한 사항

입출력 예

입력 (이진 트리 리스트) 출력 (최대 깊이)
[1, 2, 3, None, None, 4, 5] 3
[1] 1
[3, 9, 20, None, None, 15, 7] 3

입출력 설명

주어진 리스트 형식의 이진 트리에서 최대 깊이를 계산하여 반환합니다.

</aside>

풀이 1. 완전 이진 트리와 2진수의 이해

def solution(data):
    return len(bin(len(data))[2:]) **#1 노드의 총 개수를 계산**

단계별 풀이 전략

  1. 노드의 총 개수를 계산
    1. len(data) 완전 이진 트리에 있는 노드의 총 개수를 계산합니다. 예를 들어, [1, 2, 3, None, None, 4, 5]의 경우 길이는 7이 됩니다.
    2. bin(len(data)) len(data)의 결과를 2진수 문자열로 변환합니다. 예를 들어, 7의 2진수 표현은 '0b111'입니다.
    3. bin(len(data))[2:] 2진수 문자열의 앞 두 문자('0b')를 제거합니다. 예를 들어, '0b111'에서 '111'만 남깁니다.
    4. len(bin(len(data))[2:]) '111'의 길이는 '3' 입니다. 이 길이는 완전 이진 트리의 깊이(D) 와 동일 합니다. 완전 이진 트리의 깊이가 2진수 자릿수와 일치하기 때문입니다.

알아둬야 할 개념

풀이 2. 인덱스 계산

def solution(data, idx=0): **#1 매개변수**
    if idx >= len(data) or data[idx] is None: **#2 조건문**
        return 0
    else:
        left, right = 2 * idx + 1, 2 * idx + 2 **#3 자식 노드의 인덱스 계산**
        return max(solution(data, left), solution(data, right)) + 1 **#4 재귀 호출**

단계별 풀이 전략

  1. 매개변수

    data → 주어진 이진 트리의 노드를 나열한 배열입니다.

    idx → 현재 함수가 처리하고 있는 노드의 인덱스입니다. 기본 값은 0 이고, 트리의 루트 노드를 가리킵니다.

  2. 조건문

    조건문은 두 가지 경우를 확인합니다.

    1. idx >= len(data) → 현재 인덱스가 배열의 범위를 벗어난 경우입니다. 이는 주어진 인덱스에 해당하는 노드가 트리에 존재하지 않음을 의미합니다.
    2. data[idx] is None → 현재 인덱스의 노드가 None인 경우입니다. 이는 노드가 물리적으로 존재하지 않음을 나타냅니다.
    3. 위 2가지 경우 중 하나라도 참이면, 함수는 0을 반환합니다. 이는 현재 경로에서 더 이상 깊이가 증가하지 않음을 의미합니다.

  3. 자식 노드의 인덱스 계산

    이진 트리에서 부모 노드의 인덱스를 idx 라고 할 때, 왼쪽 자식 노드의 인덱스는 2 * idx + 1, 오른쪽 자식 노드의 인덱스는 2 * idx + 2 로 계산할 수 있습니다. 이 식을 이용하여, 현재 노드의 왼쪽, 오른쪽 자식 노드의 인덱스를 계산합니다.

  4. 재귀 호출

    왼쪽 자식 노드(solution(data, left))와 오른쪽 자식 노드(solution(data, right))에 대해 재귀 적으로 함수를 호출하여, 각각의 최대 깊이를 계산합니다.

    max()를 사용하여 두 자식 노드의 깊이 중 더 큰 값을 선택합니다. 이는 현재 노드를 기준으로 가장 깊은 경로의 길이를 나타냅니다. 마지막으로 현재 노드를 포함해서 깊이를 계산하기 위해 1을 추가해서 반환합니다.

알아둬야 할 개념