Given a binary tree, each node has value0
or1
. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is0 -> 1 -> 1 -> 0 -> 1
, then this could represent01101
in binary, which is13
. 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/