404. Sum of Left Leaves

Sum of Left Leaves - LeetCode

이진트리의 root가 주어진다.

주어진 트리의 왼쪽 자식 노드의 값의 합을 반환하는 문제다.

 

예시

Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

추가로 왼쪽 자식 노드의 값의 합을 반환하는 문제이기 때문에 root만 주어진다면 0을 반환해야 한다.

 

접근법

우선 재귀를 사용해서 해결할 수 있는 것 까진 문제만 읽고 감이 왔다. 어떻게 디자인을 할지 생각해보니...

결국 구하려는 값은 root의 왼쪽 subtree에 존재하는 왼쪽 자식 노드들의 값의 합 + 오른쪽 subtree에 존재하는 왼쪽 자식 노드들의 값의 합이라는 생각이 들었다. 그럼 우선 왼쪽, 오른쪽 subtree를 DFS로 탐색한 뒤 결괏값을 반환하는 구조로 디자인을 한 뒤에 조건을 맞추면 되지 않을까?라고 생각했다.

1. DFS

from typing import *


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:

        def dfs(cur, flag):

            if not cur.left and not cur.right and flag == 0:
                return cur.val

            answer = 0

            if cur.left:
                answer += dfs(cur.left, 0)

            if cur.right:
                answer += dfs(cur.right, 1)

            return answer

        return dfs(root, -1)

구현 방법은 DFS의 나름 전형적인 디자인이지만 현재 자식 노드가 부모 노드의 왼쪽 자식인지를 판단하기 위해서는 어느 방향에서 왔는지에 대한 값을 가지고 판단해줘야 한다. flag라는 값을 이용해 이를 해결했고, 초기 시작할 때는 -1로 시작하기 때문에 만약에 자식이 없는 root만 주어지는 경우도 조건문 없이 바로 적용이 가능하다.