404_Sum of Left Leaves
404. Sum of Left Leaves
Level: easy
Tag: tree
Question
Find the sum of all left leaves in a given binary tree.
Example 1
3
/ \
9 20
/ \
15 7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
Solution 1: recursive (w/o defining a helper function)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = 0
if not root:
return res
if root.left and not root.left.left and not root.left.right:
res += root.left.val
else:
res += self.sumOfLeftLeaves(root.left)
if root.right:
res += self.sumOfLeftLeaves(root.right)
return res
Solution 2: iterative (Depth first search, using stack)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = 0
stack = [root]
if not root:
return res
while stack:
node = stack.pop()
if node:
if node.right:
stack.append(node.right)
if node.left and not node.left.left and not node.left.right:
res += node.left.val
elif node.left:
stack.append(node.left)
return res
Last updated