[LeetCode 404] Sum of Left Leaves

据说是Facebook的新题，然而被LeetCode标为easy。
链接：Sum of Left Leaves
题目就是让找一棵树左叶子的总和。

想一想，不到一分钟就有了思路，果然是easy题……

第一版本：

需要判断当前走到的节点是不是为左叶子。就这一个问题。
这还不好办，来个flag标记一下，于是有了第一个AC的版本

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return helper(root, false);
    }
    
    private int helper(TreeNode node, boolean isLeft) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null && isLeft) {
            return node.val;
        }
        return helper(node.left, true) + helper(node.right, false);
    }
}

结果还不错，但是想了想，能不能把传的boolean类型去掉。
于是有了第二个AC的版本。

第二版本：

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        } else {
            sum += sumOfLeftLeaves(root.left);
        }
        sum += sumOfLeftLeaves(root.right);
        return sum;
    }
}

两个版本都是用的递归，根据LeetCode的runtime分析，第一个版本要稍微快一点。