## Friday, February 22, 2013

### [LeetCode] Sum Root to Leaf Numbers, Solution

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`.
» Solve this problem

[Thoughts]
Recursion. Similar as [LeetCode] Binary Tree Maximum Path Sum Solution, the difference here is only adding a track variable to sum all the paths.

[Code]
``````1:       int sumNumbers(TreeNode *root) {
2:            int sum=0, path =0;
3:            GenerateSum(root, sum, path);
4:            return sum;
5:       }
6:       void GenerateSum(TreeNode *root, int& sum, int path)
7:       {
8:            if(root == NULL) return;
9:            path = path*10 +root->val;
10:            if(root->left == NULL && root->right == NULL)
11:            {
12:                 sum+=path;
13:                 return;
14:            }
15:            GenerateSum(root->left, sum, path);
16:            GenerateSum(root->right, sum, path);
17:       }
``````