404.Sum of Left Leaves

Tags: [tree], [binary_tree], [tree_traversal], [traversal], [BFS]

Link: https://leetcode.com/problems/sum-of-left-leaves/?tab=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: BFS

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0

        result = 0

        # BFS
        queue = deque()
        queue.append(root)
        while queue:
            curr = queue.popleft()

            if curr.left:
                if not curr.left.left and not curr.left.right:
                    result += curr.left.val
                queue.append(curr.left)

            if curr.right:
                queue.append(curr.right)

        return result

Revelation:

• The key point is we need maintain the parent pointer, because BFS can know the relationship between parent and children, so BFS can solve this problem.
• If the single root (root.left is None and root.right is None) is also treated as the left leaf, we can modify the input checking, like following:

if not root:
    return 0
if not root.left and not root.right:
    return root.val

• Inorder traversal cannot know the real parent <=> child relationship. But preorder traversal can know the real parent <=> relationship.

Note:

• Time complexity = O(n), n is the number of nodes of the given tree.
• Space complexity = O(n), n is the number of nodes of the given tree.

Solution: binary tree traversal, preorder traversal

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0

        result = 0
        parent = None

        # preorder traversal
        stack = [root]
        while stack:
            curr = stack.pop()
            if not curr.left and not curr.right and parent and parent.left == curr:
                result += curr.val

            parent = curr
            if curr.right:
                stack.append(curr.right)
            if curr.left:
                stack.append(curr.left)

        return result

Note:

• Time complexity = O(n), n is the number of nodes in the given tree. Each node is only visited once.