2021년 3월 리커딩 챌린지 - 5일차: 두 갈래 나무의 평균 수준

오늘 우리는 3월 수업이 끝난 도전의 다섯 번째 문제를 해결할 것이다.

문제 진술

비공식 두 갈래 나무를 지정하여 각 단계의 노드의 평균값을 수조 형식으로 되돌려줍니다.
예1:

**Input:**
    3
   / \
  9  20
    /  \
   15   7
**Output:** [3, 14.5, 11]
**Explanation:**
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

솔루션

이 문제에 근거하여 우리는 두 갈래 나무의 각 등급의 평균치를 찾아야 한다.우리는 이 문제를 수평순으로 두루 훑어보는 문제로 볼 수 있다.등급 순서에 대한 더 많은 정보를 읽으십시오 here.
우리 이 문제를 상상해 봅시다.그래서 우리가 등급을 순서대로 훑어보면 각 등급의 평균치를 찾을 수 있다.이것은 매우 간단한 것 같다. 그렇지?코드 좀 봅시다.

우리는 수평 목록을 가지고 수평 총화를 저장한다.우리는 대기열을 사용하여 단계 순서를 반복합니다.우리는 우선 대기열의 크기를 검사한다. 이 크기는 두 갈래 나무의 특정 단계의 노드 수를 나타낸다.우리는 모든 노드의 값을 더해서 그것들의 평균값을 찾아 목록에 저장할 것이다.마지막으로, 우리는 목록을 되돌려줍니다.

저장소 보기