404. Sum of Left Leaves

* Recursion:

1.The core logic is to find the left leaf nodes. We could check a left leaf node by it's parents root:

root.left.left == null && root.left.right == null

2.Then we must ensure that root.left could not be null. Otherwise root.left.left or root.left.right may return NullPointerException. Similarly, we also need to write down the base condition when root == null.

3.After getting all the left node of root and calculate its sum, we just need to add it with the sumOfLeftLeaves(root.left) and sumOfLeftLeaves(root.right), and then return the final result.

• The complete code:

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

* BFS tree level traversal:

public int sumOfLeftLeaves(TreeNode root) {
    int sum = 0;
    Queue<TreeNode> q = new LinkedList<>();
    if (root != null) q.offer(root);
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        if (node.left != null) q.add(node.left);
        if (node.right != null) q.add(node.right);
        if (node.left != null && node.left.left == null && node.left.right == null) sum += node.left.val;
    }
    return sum;
}