[Easy] 404. Sum of Left Leaves

문제

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

root이진 트리가 주어지면 모든 왼쪽 잎의 합을 반환합니다.

리프는 자식이 없는 노드입니다 . 왼쪽 리프 는 다른 노드의 왼쪽 자식인 리프입니다.

 

예시

Example 1:

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.

Example 2:

Input: root = [1]
Output: 0

 

제약 조건

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -1000 <= Node.val <= 1000

 

풀이 과정

dfs 재귀를 사용하여 해결하였다.

처음에 인자로 node와 parent를 받아서 node가 parent의 left인지 확인하는 코드를 잤는데, parent가 null인 경우 parent.left도 null이 되기 때문에 런타임 에러가 발생하였다. 그래서 parent를 받는 대신 isLeft라는 인자로 대체하였다.

• dfs 탐색을 할 재귀 함수를 선언하다. 매개변수로는 node와 isLeft의 값을 받는다.
  • 만약 node의 left와 right값이 없다면 leaf 노드이다.
    • isLeft가 true라면 left leaf이기 때문에 현재 node.val을 반환한다.
    • isLeft가 false라면 0을 반환한다. (더했을 때 아무 영향이 없어야 하기 때문에)
  • leaf 노드가 아니라면 node.left와 node.right에 dfs 탐색을 진행한다.

풀이 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
    
    const dfs = (node, isLeft = false) => {
        if(!node) return 0;    
        
        //leaf인지 확인
        if(!node.left && !node.right){             
            // left인지 확인
            if(isLeft){
                return node.val; 
            }else{
                return 0;
            }
        }else{
            return dfs(node.left, true) + dfs(node.right)
        }           
    }
    
    return dfs(root)
};