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 3The 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`

.

//Will the root be NULL? //Will the result be very large? Exceed 2^23? //Will root be 0? //DFS algorithm, preorder traversal /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int sumNumbers(TreeNode* root) { return _sumNumbers(root, 0); } int _sumNumbers(TreeNode * root, int preNumber){ if(root == NULL) return 0; //leaf node if(root->left == NULL && root->right == NULL){ return preNumber * 10 + root->val; } //non-leaf node return _sumNumbers(root->left, preNumber * 10 + root->val) + _sumNumbers(root->right, preNumber * 10 + root->val); } };