sum_root_to_leaf_numbers
1from utils import TreeNode 2from typing import Optional 3 4 5# @leet start 6class Solution: 7 def sumNumbers(self, root: Optional[TreeNode]) -> int: 8 """ 9 This question asks us to return the sum of all the values in a path 10 from root to leaf. So, we can do a root to leaf traversal, aggregate 11 all the totals, and sum them up. 12 13 Normally I would check for the node to be None to return a path, but 14 that double counts paths from root to leaf, so in this case I will just traverse 15 from root to leaf and check the condition that the node is a leaf before 16 returning. 17 Finally, you can either create a new array or backtrack (using append/pop). 18 It's slightly faster when backtracking (because there's less memory usage) 19 but it's also trickier. I would prefer the extra copy version in an interview 20 and then swap to backtracking if required. 21 """ 22 nums = [] 23 24 def list_to_num(l): 25 return int("".join(map(str, l))) 26 27 def traverse(node, path): 28 if node is None: 29 return 30 path.append(node.val) 31 if node.left is None and node.right is None: 32 nums.append(list_to_num(path)) 33 path.pop() 34 return 35 traverse(node.left, path) 36 traverse(node.right, path) 37 path.pop() 38 39 traverse(root, []) 40 return sum(nums) 41 42 43# @leet end 44 45 46def test(): 47 assert 2 + 2 == 4
class
Solution:
7class Solution: 8 def sumNumbers(self, root: Optional[TreeNode]) -> int: 9 """ 10 This question asks us to return the sum of all the values in a path 11 from root to leaf. So, we can do a root to leaf traversal, aggregate 12 all the totals, and sum them up. 13 14 Normally I would check for the node to be None to return a path, but 15 that double counts paths from root to leaf, so in this case I will just traverse 16 from root to leaf and check the condition that the node is a leaf before 17 returning. 18 Finally, you can either create a new array or backtrack (using append/pop). 19 It's slightly faster when backtracking (because there's less memory usage) 20 but it's also trickier. I would prefer the extra copy version in an interview 21 and then swap to backtracking if required. 22 """ 23 nums = [] 24 25 def list_to_num(l): 26 return int("".join(map(str, l))) 27 28 def traverse(node, path): 29 if node is None: 30 return 31 path.append(node.val) 32 if node.left is None and node.right is None: 33 nums.append(list_to_num(path)) 34 path.pop() 35 return 36 traverse(node.left, path) 37 traverse(node.right, path) 38 path.pop() 39 40 traverse(root, []) 41 return sum(nums)
8 def sumNumbers(self, root: Optional[TreeNode]) -> int: 9 """ 10 This question asks us to return the sum of all the values in a path 11 from root to leaf. So, we can do a root to leaf traversal, aggregate 12 all the totals, and sum them up. 13 14 Normally I would check for the node to be None to return a path, but 15 that double counts paths from root to leaf, so in this case I will just traverse 16 from root to leaf and check the condition that the node is a leaf before 17 returning. 18 Finally, you can either create a new array or backtrack (using append/pop). 19 It's slightly faster when backtracking (because there's less memory usage) 20 but it's also trickier. I would prefer the extra copy version in an interview 21 and then swap to backtracking if required. 22 """ 23 nums = [] 24 25 def list_to_num(l): 26 return int("".join(map(str, l))) 27 28 def traverse(node, path): 29 if node is None: 30 return 31 path.append(node.val) 32 if node.left is None and node.right is None: 33 nums.append(list_to_num(path)) 34 path.pop() 35 return 36 traverse(node.left, path) 37 traverse(node.right, path) 38 path.pop() 39 40 traverse(root, []) 41 return sum(nums)
This question asks us to return the sum of all the values in a path from root to leaf. So, we can do a root to leaf traversal, aggregate all the totals, and sum them up.
Normally I would check for the node to be None to return a path, but that double counts paths from root to leaf, so in this case I will just traverse from root to leaf and check the condition that the node is a leaf before returning. Finally, you can either create a new array or backtrack (using append/pop). It's slightly faster when backtracking (because there's less memory usage) but it's also trickier. I would prefer the extra copy version in an interview and then swap to backtracking if required.
def
test():