leetcode/algorithms/python/SumRootToLeafNumbers/sumNumbers.py at master · StHamish/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"""
Method 1: dfs
"""
def sumNumbers(self, root):
    if not root: return 0
    stack, res = [(root, root.val)], 0
    while stack:
        node, value = stack.pop()
        if not node.left and not node.right:
            res += value
        if node.right:
            stack.append((node.right, value * 10 + node.right.val))
        if node.left:
            stack.append((node.left, value * 10 + node.left.val))
    return res


"""
Method 2: recursive solution
"""
def sumNumbers(self, root):
    return self.helper(root, 0)

def helper(self, node, s):
    if not node: return 0
    if not node.left and not node.right: return s * 10 + node.val
    return self.helper(node.left, s * 10 + node.val) + \
            self.helper(node.right, s * 10 + node.val)