본문 바로가기

알고리즘

이진 트리의 최대 깊이 찾기

Basic 100 · 47번Lv. 2자료 구조·클래스

이진 트리의 최대 깊이 찾기

문제 설명

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

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

    1
   / \
  2   3
       / \
     4   5

제한 사항

  • 트리의 노드 수는 1 이상 10,000 이하입니다.
  • 각 노드의 값은 -10,000 이상 10,000 이하의 정수 또는 None입니다.
  • 리스트 끝에 None이 붙어 있을 수 있습니다. None인 자리는 노드가 없는 것으로 보고 깊이에 세지 않습니다.

입출력 예

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

입출력 설명

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

예시 테스트

#입력기대값
1[1, 2, 3, null, null, 4, 5]3
2[1]1
3[3, 9, 20, null, null, 15, 7]3

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 11개도 함께 채점해요.