[leetcode #404] Sum of Left Leaves

Problem

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

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

Idea

left leaf node의 합을 구하라는 문제다. Tree를 탐색해야 하기 때문에 재귀함수를 쓰는 건 기본이다. 재귀함수에서 flag를 둬서 left child일 때만 sum을 계산할 수도 있지만, 최근에 읽은 'Clean Code'에서 flag 사용을 지양하고 새로운 함수를 만들라길래 그렇게 해봤다. left child일 경우 leaf node인지 확인하고 값을 더하고, right child인 경우는 그냥 재귀함수를 호출하면 된다.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return traverseTreeForRight(root);
    }

    private int traverseTreeForRight(TreeNode node) {
        if (node == null)
            return 0;

        return traverseTreeForLeft(node.left) + traverseTreeForRight(node.right);
    }

    private int traverseTreeForLeft(TreeNode node) {
        if (node == null)
            return 0;

        if (node.left == null && node.right == null)
            return node.val;

        return traverseTreeForLeft(node.left) + traverseTreeForRight(node.right);
    }
}

Reference

https://leetcode.com/problems/sum-of-left-leaves/