'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    
    # recursive
    def sumRootToLeaf2(self, root: TreeNode) -> int:
        def preorder(node, curr_number):
            nonlocal root_to_leaf
            if node:
                curr_number = (curr_number << 1) | node.val
                # if it's a leaf, update root-to-leaf sum
                if not (node.left or node.right):
                    root_to_leaf += curr_number
                    
                preorder(node.left, curr_number)
                preorder(node.right, curr_number) 
        
        root_to_leaf = 0
        preorder(root, 0)
        return root_to_leaf
    
    # official, iterative
    def sumRootToLeaf1(self, root: TreeNode) -> int:
        root_to_leaf = 0
        stack = [(root, 0) ]
        
        while stack:
            root, curr_number = stack.pop()
            if root is not None:
                curr_number = (curr_number << 1) | root.val # nice!
                # if it's a leaf, update root-to-leaf sum
                if root.left is None and root.right is None:
                    root_to_leaf += curr_number
                else:
                    stack.append((root.right, curr_number))
                    stack.append((root.left, curr_number))
                        
        return root_to_leaf
    
    # self-made; T: O(N); S: O(H)
    def sumRootToLeaf(self, root: TreeNode) -> int:
        
        if not root: return 0
        
        res = []
        # dfs(root, "")
        stack = [(root, "")]
        while stack:
            node, path = stack.pop()
            if node:
                path += str(node.val)
                if node.left:
                    stack.append((node.left, path)) 
                if node.right:
                    stack.append((node.right, path)) 
                if not node.left and not node.right:
                    res.append(path)
        
        return sum([int(v, 2) for v in res])