LeetCode 풀기 - 1302. Deepest Leaves Sum

1302. Deepest Leaves Sum

https://leetcode.com/problems/deepest-leaves-sum/

Deepest Leaves Sum - LeetCode

문제)

솔루션1)

hashtable을 사용해서 각 depth의 노드에 해당하는 모든 val 값들을 list 형태로 저장한다. hashtable에서 최대 depth에 O(1)로 접근해서 모든 values의 sum을 구하면 그것이 deepest leaves의 합이된다.

# 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)