""" 0404.1 - Solution 1 - Recursive DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""Binary Tree Node"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
"""Sum of Left Leaves Function"""
if not root:
return 0
total = 0
# Check if left child is a leaf
if root.left and not root.left.left and not root.left.right:
total += root.left.val
else:
total += self.sumOfLeftLeaves(root.left)
total += self.sumOfLeftLeaves(root.right)
return total
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: [3,9,20,null,null,15,7] -> 24
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(Solution().sumOfLeftLeaves(root)) # 24
# Example 2: [1] -> 0
root2 = TreeNode(1)
print(Solution().sumOfLeftLeaves(root2)) # 0
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0404.2 - Solution 2 - Iterative BFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""Binary Tree Node"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
"""Sum of Left Leaves Function"""
if not root:
return 0
total = 0
queue = deque([root])
while queue:
node = queue.popleft()
if node.left:
if not node.left.left and not node.left.right:
total += node.left.val
else:
queue.append(node.left)
if node.right:
queue.append(node.right)
return total
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: [3,9,20,null,null,15,7] -> 24
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(Solution().sumOfLeftLeaves(root)) # 24
# Example 2: [1] -> 0
root2 = TreeNode(1)
print(Solution().sumOfLeftLeaves(root2)) # 0
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
