aboutsummaryrefslogtreecommitdiff
path: root/sum_left_leaves.py
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