## Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
    1
/ \
2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

### Analysis:

Once we see this kind of problem, no matter what sum is required to output, "all root-to-leaf" phrase reminds us the classic Tree Traversal or Depth-First-Search algorithm. Then according to the specific problem, compute and store the values we need. Here in this problem, while searching deeper, add the values up (times 10 + current value), and add the sum to final result if meet the leaf node (left and right child are both NULL).

### Code(C++):

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:

void dfs(TreeNode* root,int cur, int &res){
if (root->left==NULL && root->right==NULL){
cur=cur*10+root->val;
res+=cur;
}else{
cur=cur*10+root->val;
if (root->left){
dfs(root->left,cur,res);
}
if (root->right){
dfs(root->right,cur,res);
}
}
}
int sumNumbers(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int res=0;
if (!root){return res;}
dfs(root,0,res);
return res;
}
};


### Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param root, a tree node
# @return an integer
res = 0
def search(self, root, path):
if root.left == None and root.right == None:
self.res += path + root.val
else:
if root.left != None:
self.search(root.left, (path + root.val)*10)
if root.right != None:
self.search(root.right, (path + root.val)*10)

def sumNumbers(self, root):
self.res = 0
if root == None:
return 0
else:
self.search(root, 0)
return self.res