Given a binary tree, each node has value
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
01101in 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.
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
xwould 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)