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 -&gt; 2 -&gt; 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.

&nbsp;
Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1-&gt;2 represents the number 12.
The root-to-leaf path 1-&gt;3 represents the number 13.
Therefore, sum = 12 + 13 = 25.


Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4-&gt;9-&gt;5 represents the number 495.
The root-to-leaf path 4-&gt;9-&gt;1 represents the number 491.
The root-to-leaf path 4-&gt;0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 1000].
	0 &lt;= Node.val &lt;= 9
	The depth of the tree will not exceed 10.


# 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: Optional[TreeNode]) -> int:
        
        int_list = []
        
        def traverse(node, input_string):
            
            nonlocal int_list
            
            if not node:
                return int_list
            
            input_string = input_string + str(node.val)

            if not (node.left or node.right):
                int_list.append(int(input_string))
            
            traverse(node.left, input_string)
            traverse(node.right, input_string)
                
        traverse(root, "")
        return sum(int_list)
                
class Solution {
    int res;
    public int sumNumbers(TreeNode root) {
        res = 0;
        getSum(root, 0);
        
        return res;
    }
    
    public void getSum(TreeNode root, int sum){
        
        if(root.left == null && root.right == null) {
            res += (sum*10+root.val);
        }
        
        if(root.left != null)
            getSum(root.left, sum*10+root.val);
        
        
        if(root.right != null)
            getSum(root.right, sum*10+root.val);
    }
}
class Solution {
public:
    int ans=0;
    void dfs(TreeNode* root, string s){
        if(!root->left && !root->right){
            s+=to_string(root->val);
            ans+=stoi(s);
            return;
        }
        string o = s;
        s+=to_string(root->val);
        if(root->left) dfs(root->left,s);
        if(root->right) dfs(root->right,s);
        s=o;

    }
    int sumNumbers(TreeNode* root) {
        if(!root) return ans;
        string s = "";
        dfs(root,s);
        return ans;
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    return dfs(root)
};

const dfs = (root, path = '') => {
    if (!root.left && !root.right) return +(path + root.val)
    
    const left = root.left ? dfs(root.left, path + root.val) : 0
    const right = root.right ? dfs(root.right, path + root.val) : 0
    
    return left + right
}
Sum Root to Leaf Numbers