[Leetcode]1022. Sum of Root To Leaf Binary Numbers

Given a binary tree, each node has value 0 or 1.  Each root-to-leaf path represents a binary number starting with the most significant bit.  For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.
For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.
Return the sum of these numbers.

Brute force

We can use Preorder Tree Traversal to search the entire binary tree, recording the path and convert it to numbers with base 10. More info about Preorder/Inorder/Postorder Tree Traversal could be found in the reference.

class Solution:
    def sumRootToLeaf(self, root: TreeNode) -> int:
        if not root:
            return 0
        ret = []
        def helper(node,path):
            path += str(node.val)
            if not node.left and not node.right:
                ret.append(int(path,2))
                return
            if node.left:
                helper(node.left,path)
            if node.right:
                helper(node.right,path)
        helper(root,'')
        return sum(ret)

Optimized – bit operations and count along DFS

Here are two optimisations we can make:

• Instead of using string to append the bit one by one, we can use bit operations – shift – to count the values with the base 10. Here left shifting x would multiply the number by 2^x and | (or) would do the addition.
• We can count the values along with the searching.

class Solution:
    def sumRootToLeaf(self, root: TreeNode) -> int:
        def helper(node,cur):
            if not node: return 0
            cur = cur << 1 | node.val
            if node.left is None and node.right is None: return cur
            return helper(node.left,cur) + helper(node.right,cur)
        return helper(root,0)

Reference

• https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/
• https://shawnlyu.com/algorithms/tree-traversal-recursively-iteratively-preorder-inorder-postorder/