Problem

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

思路一（bfs）

• if root node is the only one node, it doesn't count as left leave node
• Given the current node, determine if cur.left != null,
  • if yes, if cur.left.left == null && cur.left.right == null, add to sum
  • else if no, add to queue
• if cur.right != null, add to queue

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

思路二（divide and conquer）

• if root node is the only one node, it doesn't count as left leave node
• Given the current node, determine if cur.left != null,
  • if yes, if cur.left.left == null && cur.left.right == null, add to sum
  • else if no, recursively find it
• if cur.right != null, recursively find it

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;

        int sum = 0;

        if (root.left != null) {
            if (root.left.left == null && root.left.right == null) {
                sum += root.left.val;        
            } else {
                sum += sumOfLeftLeaves(root.left);
            }
        }
        if (root.right != null) {
            sum += sumOfLeftLeaves(root.right);
        }
        return sum;
    }