Solution to LeetCode Problems: Sum Root to Leaf Numbers

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.

Thoughts:
Traverse the binary tree by depth-first and record the numbers. When the leaf is met, the accumulated value is added up.


Solution:

1. /** 
2.  * Definition for binary tree 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
8.  * }; 
9.  */  
10. class Solution {  
11. public:  
12.     int Sum;  
13.       
14.     void TraverseProc(const TreeNode* node, int value)  
15.     {  
16.         const int VAL = value * 10 + node->val;  
17.           
18.         if (node->left == nullptr && node->right == nullptr)  
19.             Sum += VAL; // at a leaf  
20.         else  
21.         {  
22.             if (node->left != nullptr)  
23.                 TraverseProc(node->left, VAL);  
24.             if (node->right != nullptr)   
25.                 TraverseProc(node->right, VAL);  
26.         }  
27.     }  
28.   
29.     int sumNumbers(TreeNode *root) {  
30.         Sum = 0;  
31.         if (root != nullptr)  
32.             TraverseProc(root, 0);  
33.         return Sum;  
34.     }  
35. };