[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


これは左葉ノードの和を求める問題である.Treeを探索するため,再帰関数を用いることが基本である.再帰関数にflagを配置しleft child時のみsumを計算することができますが、最近読んだ「Clean Code」ではflagの使用を避けて新しい関数を作成するよう求められていたので、このようにしました.left childの場合、leafノードであるかどうかを確認し、値を追加します.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/