404. Sum of Left Leaves
[Sum of Left Leaves - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com](https://leetcode.com/problems/sum-of-left-leaves/)
이진트리의 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만 주어지는 경우도 조건문 없이 바로 적용이 가능하다.