DEV Community

loading...

Sum of Left Leaves - Leetcode

Shirley
Software engineer | Full stack developer | Javascript && Python
・1 min read

Today's leetcode challenge was a binary tree question: sum all of the left leaves of a binary tree.

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.
Enter fullscreen mode Exit fullscreen mode

My method was using dfs and recursion. I created a dfs function that had two parameters: a value for the node (root) and a boolean value for whether the node was left or not(left). Then I checked to see if the root had a left child or right child and if it was left. If true, I added the value of the node to a cache. I then used recursion to loop through all the left nodes and all the right nodes. In my main function, I set cache = [0] and called the dfs function with parameters of root, and False.

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        def dfs(root, left):
            if not root:
                return
            if left and not root.left and not root.right:
                cache[0] += root.val
            dfs(root.left, True)
            dfs(root.right, False)
        cache = [0]
        dfs(root, False)
        return cache[0]
Enter fullscreen mode Exit fullscreen mode

Discussion (0)