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 += root.val dfs(root.left, True) dfs(root.right, False) cache =  dfs(root, False) return cache
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).
lev? Is that debug stuff you forgot to take out? :-)
Haha yes, thank you
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)
@agave Nice! But why
cache can deliver its value in the recursive process? Is this the property of a
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?
@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.right can only be the same object if they're both
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.