subject :
Give you the root node of a binary tree root , Each node in the tree stores a 0 To 9 Number between .
Each path from the root node to the leaf node represents a number :
for example , Path from root node to leaf node 1 -> 2 -> 3 Representation number 123 .
Calculates the generated from the root node to the leaf node The sum of all the figures .
Leaf nodes A node without children .
Example 1:
Input :root = [1,2,3]
Output :25
explain :
Path from root to leaf node 1->2 On behalf of the digital 12
Path from root to leaf node 1->3 On behalf of the digital 13
therefore , Sum of numbers = 12 + 13 = 25
Example 2:
Input :root = [4,9,0,5,1]
Output :1026
explain :
Path from root to leaf node 4->9->5 On behalf of the digital 495
Path from root to leaf node 4->9->1 On behalf of the digital 491
Path from root to leaf node 4->0 On behalf of the digital 40
therefore , Sum of numbers = 495 + 491 + 40 = 1026
Code :
# 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:
def sumNumbers(self, root: TreeNode) -> int:
def dfs (root, res):
if not root:
return 0
res = res*10 + root.val
if not root.left and not root.right:
return res
else:
return dfs(root.left, res) + dfs(root.right, res)
return dfs(root, 0)