blob: 6f1fac97d3f6fe3cd67a2788316a0cbc740e368f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
# 404. Sum of Left Leaves
from collections import deque
"""
given the 'root' of a binary tree, return the sum of all left leaves. a leaf
is a node with no childen. a leaft leaf is a leaf that is the left child of
another node.
"""
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
s, ans = deque([(root, False)]), 0
while s:
curr, is_left = s.pop()
if not curr.left and not curr.right and is_left:
ans += curr.val
if curr.right:
s.append((curr.right, False))
if curr.left:
s.append((curr.left, True))
return ans
|