404. Sum of Left Leaves

Math, Binary Search, Review · 13 Dec 2023

Problem Statement

link: LeetCode.cn LeetCode

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Example:

Input: root = [3,9,20,null,null,15,7] Output: 24

Input: root = [1] Output: 0

Solution Approach

bfs or dfs

Algorithm

BFS Variant:

Implement a BFS using a deque. Traverse the tree, tracking if a node is a leaf and if it’s a left leaf. Accumulate the values of left leaves.

Recursive DFS:

Implement a recursive DFS function. Traverse the tree, checking if each node is a leaf and if it’s a left leaf. Accumulate the values of left leaves.

Implement

    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):
      if not root:
        return 0
      isLeaf = lambda node: not node.left and not node.right
      q = collections.deque(root)
      res = 0
      while q:
        node = q.popleft()
        if node.left:
          if isLeaf(node.left):
            res += node.left.val

class Solution:
    def sumOfLeftLeaves(self, root):
      def isLeaf(node):
        if not node.left and not node.right:
           return True
        else:
            return False

      def dfs(node):
        res = 0
        if node.left:
          if isLeaf(node.left):
            res += node.left.val
          else:
            res += dfs(node.left)
        if node.right:
          if not isLeaf(node.right):
            res += dfs(node.right)
        return res
      return dfs(root) if root else 0