Deepest Leaves Sum

첫번쨰 코드

 

트리 class를 다루는 경우는 처음이어서,

gpt에게 설명을 들으면서 코드를 적어나갔다.

 

여기서 정리할 것은, 주어진 트리는 TreeNode 클래스를 사용하여 정의

- 트리의 각 노드는 val이라는 값

- 왼쪽 자식 노드를 가리키는 left

- 오른쪽 자식 노드를 가리키는 right

 

코드 자체는 BFS를 이용하여 작성하였다.

root를 시작으로 해당 값을 더한 후

left나 right가 있으면 다시 넣은 후, sum을 다시 0으로 만드는 과정을 반복한다.

 

만약에 left나 right가 더 이상 아무것도 없으면

해당 값은 마지막 leave로 가장 깊은 node가 될 것이다.

 

# 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

from collections import deque

class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        queue = deque([root])
        answer = 0

        while queue:
            now_sum = 0
            level_size = len(queue)

            for _ in range(level_size):
                node = queue.popleft()
                now_sum += node.val

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
            answer = now_sum

        return answer

 

통과!

더 많은 트리 문제를 풀어보고

나아가 혼자서도 풀 수 있도록 코드를 작성해야 할 것이다.

 

또한 위 문제를 저렇게 말고 다른 리스트를 만들어 해당 노드 마다 깊이를 세어

깊이가 가장 큰 값의 node값을 더하는 방법으로도 풀 수 있지 않을까?

---

링크

https://github.com/ornni/leetcode/tree/main/1302-deepest-leaves-sum

leetcode/1302-deepest-leaves-sum at main · ornni/leetcode