Sum of Root To Leaf Binary Numbers

Problem Id: 1022 Difficulty: Easy Tag: Tree


Intuition

This problem could be solved by following steps.

  1. Maintain the target value during the process of DFS.
  2. Once we visit a leaf node, add the value to the sum of all values.

Solution


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

class Solution:
    def sumRootToLeaf(self, root: TreeNode) -> int:
        self.target_sum = 0
        self._helper(root, 0)
        return self.target_sum

    def _helper(self, node, previous):
        if node is None:
            return

        current = (previous << 1) + node.val
        if node.left is None and node.right is None:
            self.target_sum += current
        else:
            self._helper(node.left, current)
            self._helper(node.right, current)