📃 문제 설명

Deepest Leaves Sum

[문제 출처 : LeetCode]

👨‍💻 해결 방법

이진 트리가 주어지는데,
최대 깊이에 있는 노드들의 값의 합을 구하는 문제.

우선 트리의 깊이(높이)를 구하기 위해 stack을 사용하여 dfs를 구현했고, stack에 노드의 깊이를 함께 저장했다.

그리고 자식이 없는 리프 노드가 나올 때마다 해당 깊이를 key로 하는 딕셔너리에 노드의 값을 더해줬다.

dfs을 끝내고 나면 딕셔너리에 깊이가 같은 리프노드끼리의 합이 저장되어 있다.
딕셔너리의 key값은 트리의 깊이이므로 딕셔너리를 내림차순 정렬하여, 가장 앞에 있는 value를 반환.

👨‍💻 소스 코드

# 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:
        stack = [(root, 0)]
        leaf = {}

        while stack:
            node = stack.pop()

            if node[0].left:
                stack.append((node[0].left, node[1] + 1))
            if node[0].right:
                stack.append((node[0].right, node[1] + 1))
            if not (node[0].left or node[0].right):
                if node[1] in leaf:
                    leaf[node[1]] += node[0].val
                else:
                    leaf[node[1]] = node[0].val

        return sorted(leaf.items(), reverse = True)[0][1]