Short Python


  • 4
    class Solution(object):
        def sumOfLeftLeaves(self, root):
            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]
    

    Complexity is O(n) time and O(n) space. This is because we use DFS so it takes stack space proportional to height of tree (which is n in the worst case).


  • 0

    lev? Is that debug stuff you forgot to take out? :-)


  • 0

    @StefanPochmann said in Short Python:

    lev? Is that debug stuff you forgot to take out? :-)

    Haha yes, thank you


  • 2

    Bit different, including one of my favorite tricks:

    def sumOfLeftLeaves(self, root):
        def dfs(root, left=False):
            if not root: return 0
            if left and root.left is root.right: 
                return root.val
            return dfs(root.left, True) + dfs(root.right)
        return dfs(root)

  • 0
    C

    @agave Nice! But why cache can deliver its value in the recursive process? Is this the property of a list?


  • 0
    Z

    @ManuelP

    Your solution seem very nice.

    Could you explain
    what is the meaning of
    if left and root.left is root.right:

    here, could you explain it?


  • 2

    @zjlncsu That tells me whether the current root is a left leaf. The left tells me whether it's a left child, and the root.left is root.right tells me whether it's a leaf (because root.left and root.right can only be the same object if they're both None).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.