LeetCode 637. Average of Levels in Binary Tree (python)

 

 

풀이

 

이진트리가 주어지고, 각 깊이 레벨의 해당하는 값들의 평균값을 구하는 문제

 

각 트리를 재귀로 탐색하고, 각각의 값을 리스트에 레벨에 맞는 인덱스에 값을 모두 더 해준 뒤

 

레벨의 개수 별로 나눠주면 되는 문제이다.

 

 

 

코드

class Solution(object):
    def averageOfLevels(self, root):
        self.depth = 0	#깊이 체크 포인터
        self.result=[]	# 레벨별로 값이 담길 리스트
        self.count =[]	# 레벨별로 개수가 담길 리스트
        self.find(root,0) # 시작
        for i in range(len(self.result)):	# 구해진 값들을 result(레벨별 총합)/count(레벨별 개수)
            self.result[i]= float(self.result[i])/float(self.count[i])
         
    
        return self.result # 나눠진 값이 담긴 리스트 리턴 
            
    def find(self,node,depth):
        if node== None:	# node가 비었다면 return 
            return
        if len(self.result)==depth: # 깊이와 레벨이 같다면 각 리스트의 길이 추가
            self.result.append(node.val)
            self.count.append(1)
        else:
            self.result[depth]+=node.val # 다르다면 레벨에 맞게 result와 count에 값 추가
            self.count[depth]+=1
        self.find(node.left,depth+1) #재귀적으로 left,right 탐색 
        self.find(node.right,depth+1)

 

1. 레벨별 총합을 넣을 리스트 (result), 레벨별 개수를 넣을 리스트 count를 만든다.

2. find함수로 각 레벨별로 탐색을하며 깊이가 깊어질때마다 depth값을 +1 해준다.

3. depth값을 기반으로 최초 탐색시 len(self.result)와 depth가 같아지는 순간 리스트 공간 추가 

4. depth와 len길이가 다르다면 , 각 리스트 인덱스 (depth)를 통해서 값 더해주고, 개수 추가해주기,

5. 탐색이 끝난 후 각 인덱스별로 나눠준 뒤 리턴

def averageOfLevels(self, root):
    info = []
    def dfs(node, depth = 0):
        if node:
            if len(info) <= depth:
                info.append([0, 0])
            info[depth][0] += node.val
            info[depth][1] += 1
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
    dfs(root)

    return [s/float(c) for s, c in info]

리스트를 하나를 사용하여 각 인덱스에 값과 개수를 추가해서 사용한다.

 

방법은 내가 사용한 방법이랑 같지만, 코드가 간결하고 공간복잡도가 줄어든 코드이다.

 

튜프을 사용해서 (값,개수)로 각 인덱스에 값을 갱신해줬다.