[스파르타] 99클럽 2기 코테스터디 13일차 TIL / leet 1302

LeetCode: 1302. Deepest Leaves Sum (링크)

1302. Deepest Leaves Sum

 

Leetcode 저번에 처음 풀어봤는데 아직도 사용법이 익숙해지지 않은 것 같다. 문제를 요약하자면 다음과 같다. root 변수에 리스트를 주고 이걸 트리 구조로 만든 후 제일 깊은 레벨의 노드들의 합을 구하는 문제였다.

 

당연히 입력값은 리스트만 주어지고 이걸 트리로 구현하는 것부터 시작이라고 생각했는데, 다른 사람의 풀이를 참고하니 이미 트리는 만들어진 상태였다. 그냥 노드들을 돌면서 왼쪽, 오른쪽 자식이 있는지 확인하고 있다면 next_nodes라는 빈 리스트에 다음에 확인할 노드들을 넣어주면 됐다. level_sum은 계속 초기화되니까 결국 마지막 출력값은 제일 깊은 레벨의 노드들을 더한 값과 같아진다. 다만 이해가 안 가는 부분은 제일 처음에 q = [root]를 하게 되면 q = [[1, 2, 3,... ]] 이런 식으로 주어질 텐데 level_sum += node.val이 어떻게 진행되는지 모르겠다. 이 root 값이 그냥 1만 있다면 알 것 같은데 어떻게 여러 개의 요소가 있는 리스트에 .val, .left, .right가 되는 걸까? 우선은 1만 있다고 간주하고 이해했다.

 

다른 한국인 분의 풀이도 찾아봤다. 이 분은 같은 레벨의 노드들을 각각 hashtable로 저장하고 모든 저장이 끝난 뒤, 최종으로 제일 깊은 레벨의 합만 찾는 방식으로 풀이하셨는데 더 이해하기 좋았다. 

 

## 풀이 (1)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        q = [root]
        while q:
            level_sum = 0
            next_nodes = []
            for _ in range(len(q)):
                node = q.pop()
                level_sum += node.val
                if node.left:
                    next_nodes.append(node.left)
                if node.right:
                    next_nodes.append(node.right)

            q = next_nodes
        return level_sum
        
        
## 풀이 (2)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:        
        d = defaultdict(int)
        self.traverse(root, 1, d)
        
        max_depth = max(d.keys())
        return d[max_depth]
        
    def traverse(self, node, depth, d):
        if node is None:
            return         
        
        d[depth] += node.val
        self.traverse(node.left, depth+1, d)
        self.traverse(node.right, depth+1, d)

오늘 미들러 풀이 끝!

---

참고한 풀이: https://leetcode.com/problems/deepest-leaves-sum/solutions/5237243/python-bfs/

참고한 블로그: https://wellsw.tistory.com/74?category=1054641

LeetCode 풀기 - 1302. Deepest Leaves Sum