###### tags: `Leetcode` `medium` `tree` `dfs` `python`

# 129. Sum Root to Leaf Numbers

## [題目連結:] https://leetcode.com/problems/sum-root-to-leaf-numbers/

You are given the root of a binary tree containing digits from ```0 to 9``` only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path ```1 -> 2 -> 3``` represents the number ```123```.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a **32-bit** integer.

A **leaf** node is a node with no children.


#### [圖片來源:] https://leetcode.com/problems/sum-root-to-leaf-numbers/

## 解題想法:
* 題目為，求root到各leaf之路徑和，且每一層相當於val*10
* dfs遞迴求解:
* 每次傳當前root.val*10到下一層

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertLeft(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res=0
        self.dfs(root,0)
        return self.res
    def dfs(self,root,curSum):
        if not root:
            return
        curSum*=10
        curSum+=root.val
        #leaf
        if not root.left and not root.right:
            self.res+=curSum
            return
        self.dfs(root.left,curSum)
        self.dfs(root.right,curSum)

root=TreeNode(4)
root.insertLeft(9)
root.insertRight(0)
root.left.insertLeft(5)
root.left.insertRight(1)
print("Original:",end='')
root.printTree() #Original:[4, 9, 0, 5, 1]

result = Solution()
ans = result.sumNumbers(root)
print(ans) #1026