404.sum-of-left-leaves.md

404. Sum of Left Leaves

Test Cases

Normal Cases

Input: 
        1
      /   \
     3     5
         /   \
        4     7
Output: 3 + 4

Edge / Corner Cases

Input: 1
Output: 0

Input: 
    1
  /   
 2
Output: 2

Input:
    1 
      \
       2
Output: 0

Input:
        1
      /   \
     2     4
    /     / 
   3     6
Output: 3 + 6

    1
  /   \
 3     4
      / 
     6
      \ 
       9
Output: 3, but 6 and 9 are not left leaf node.

Input:
    1
  /   \
 3     4
   \
    5
   /
  9
Output: 9, but 3 is not left leaf node.

Approach

Overall, there are two approaches to solve this problem:

• We traversal every node, and check if the left child of the node is a leaf node.

fun dfs(root: TreeNode?, isLeft: Boolean): Int {
    if (root.isLeaf() && isLeaft) {
        sum += root.`val`
    }
    // ... other code
    return sum
}

• For each node, we check its left child is a leaf node or not.

fun dfs(root: TreeNode?): Int {
    if (root.left != null) {
        if (root.left.isLeaf()) {
            sum += root.left.`val`
        } else {
            sum += dfs(root.left)
        }
    }
    // ... other code
    return sum
}

Then we can solve this problem via recursive or iterative way.

Top-Down Recursive

private var sum = 0
fun sumOfLeftLeaves(root: TreeNode?): Int {
    dfs(root, null)
    return sum
}

// dfs() function does not return the sum, we update via a global variable
private fun dfs(root: TreeNode?, parent: TreeNode?) {
    if (root == null) return
    if (root.left == null && root.right == null && parent?.left == root) {
        sum += root.`val`
        return
    }
    dfs(root.left, root)
    dfs(root.right, root)
}

// Or equivalently, dfs() function returns the sum
fun sumOfLeftLeaves(root: TreeNode?): Int {
    return dfs(root, null)
}

private fun dfs(root: TreeNode?, parent: TreeNode?): Int {
    if (root == null) return 0
    if (root.left == null && root.right == null && parent?.left == root) {
        return root.`val`
    }
    return dfs(root.left, root) + dfs(root.right, root)
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Iterative

We just use iterate template to traverse the tree, we enqueue node with isLeft state and check if the current node is a left leaf node.

 fun sumOfLeftLeaves(root: TreeNode?): Int {
    if (root == null) return 0
    var sum = 0
    // It's ok to use Stack
    val queue = ArrayDeque<Pair<TreeNode, Boolean>>() 
    queue.addLast(root to false)
    while (queue.isNotEmpty()) {
        val pair = queue.removeFirst()
        val node = pair.first
        val isLeft = pair.second
        if (node.left == null && node.right == null && isLeft) {
            sum += node.`val`
        }
        if (node.left != null) {
            queue.addLast(node.left to true)
        }
        if (node.right != null) {
            queue.addLast(node.right to false)
        }
    }
    return sum
}

Or we don't enqueue node with isLeft state, we check if left child of every node is a left leaf node and sum it.

fun sumOfLeftLeaves(root: TreeNode?): Int {
    if (root == null) return 0
    var sum = 0
    // It's ok to use Stack
    val queue = ArrayDeque<TreeNode>() 
    queue.addLast(root)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        if (node.left != null) {
            if (node.left.isLeaf()) {
                sum += node.left.`val`
            } else {
                queue.addLast(node.left)
            }
        }
        if (node.right != null) {
            queue.addLast(node.right)
        }
    }
    return sum
}