# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
# time O(N) space O(1)
# step1 initialize total, check if root empty, if not, enter recursion
self.total = 0
if not root:
return self.total
self._traverse(root)
return self.total
def _traverse(self,node):
# step2 check if there is node.left; if yes, check if it's leaf node
if node.left:
# check if they are leaves on the left node
if not node.left.left and not node.left.right:
self.total += node.left.val
else:
self._traverse(node.left)
#step3 check if there is right node, if yes recurse from node.right
if node.right:
self._traverse(node.right)
iterative solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
# main idea: check if node.left is leaf node, if yes add its val into sum. if not, push only left child into stack; for right node, check if it not leaf node, if not, push its children into stack
# time O(N) space O(N)
sum = 0
if not root:
return sum
stack = [root]
while stack:
node = stack.pop()
if node.left:
if not node.left.left and not node.left.right:
sum += node.left.val
else:
stack.append(node.left)
if node.right and (node.right.left or node.right.right):
stack.append(node.right)
return sum