[2024] day 106. Leetcode 404. Sum of Left Leaves

gunny·2024년 4월 18일

leetcode 404. Sum of Left Leaves leetcode 404. Sum of Left Leaves python

코딩테스트

목록 보기

419/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 14일 (일)
Leetcode daily problem

404. Sum of Left Leaves

https://leetcode.com/problems/sum-of-left-leaves/?envType=daily-question&envId=2024-04-14

Problem

이진 트리가 주어질 때, 모든 왼쪽 터미널 노드의 합을 반환한다.

Solution

DFS(Depth-first Search, 깊이 우선 탐색)

이진 트리를 순환하면서, 먼저 left 노드가 있는지 체크한다.
left 노드가 있다면 해당 left 노드가 터미널 노드 인지 확인하기 위해서 left노드의 left, right 노드가 있는지 없는지 여부를 판단한다.
만약 left노드의 left, right가 각각 None 이라면 left노드가 왼쪽에 있는 터미널 노드임을 의미하므로 해당 left 노드의 값을 합하여 업데이트 한다.

만약, left 노드가 존재하지만 left 혹은 right 노드가 하나라도 None이 아니라면 터미널 노드가 아님을 의미하므로, 구하고자 하는 것은 left 쪽의 터미널 노드이므로 left 노드의 left (root 기준 root.left.left)를 재귀로직을 태워서 윗 스텝에서의 left 의 터미널 노드의 합을 업데이트 한다.

left로 계속 이동해서 left의 끝에 도달하면 root 노드 기준 right에 있는 노드 또한 left 노드의 터미널이 존재할 수 있으므로, root.right을 재귀로직을 태워 합을 업데이트 한다.

root node에서 모든 로드를 탐색했다면 합을 반환한다.

Code


# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        ans = 0
        if not root:
            return 0
        
        if root.left:
            if not root.left.left and not root.left.right:
                ans += root.left.val

            else:
                ans += self.sumOfLeftLeaves(root.left)
        
        ans += self.sumOfLeftLeaves(root.right)

        return ans