Problem description
Find the sum of all left leaves in a given binary tree.
Example:
3
/ \
9 20
/ \
15 7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
Solution
We do post order traversal of the tree. For each node, we check whether its left child is leaf(that means node.left.left == None and node.left.right == None). If it is leaf, we add the val of its left child to the ans.
Below is python implementation
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
self.sum = 0
def dfs(root: TreeNode)->None:
if not root:
return
dfs(root.left)
dfs(root.right)
if root.left and root.left.right == None and root.left.left == None:
self.sum += root.left.val
dfs(root)
return self.sum