[Python] leetcode-1302.Deepest Leaves Sum(DFS)

문제 설명

Given the root of a binary tree, return the sum of values of its deepest leaves.

---

제한 사항

• The number of nodes in the tree is in the range [1, 10^4].
• 1 <= Node.val <= 100

---

입출력 예제

root	return
[1,2,3,4,5,null,6,7,null,null,null,null,8]	15
[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]	19

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:
        def dfs(root,level):
            # null일 경우에는 실행안함
            if not root:
                return
            # root가 같다면 자식들끼리 값을 합산
            d[level]+=root.val
            # 왼쪽부터 재귀함수 실행
            dfs(root.left,level+1)
            # 그 후에 오른쪽 재귀함수 실행
            dfs(root.right,level+1)
        # 딕셔너리에 초기화를 신경쓰지 않고 값 추가
        d=defaultdict(int)
        dfs(root,0)
        #가장 깊은 레벨 찾기
        mx=max(d)
        # 깊은 레벨에 value가 몇인지 반환
        return d[mx]

결과