# LeetCode 129. Sum Root to Leaf Numbers

## Description:

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.

## Example:

input:

    1
/ \
2   3


output:

25

explanation:

The root-to-leaf path 1->2 represents the number 12.

The root-to-leaf path 1->3 represents the number 13.

Therefore, sum = 12 + 13 = 25.

input:

    4
/ \
9   0
/ \
5   1


output:

1026

explanation:

The root-to-leaf path 4->9->5 represents the number 495.

The root-to-leaf path 4->9->1 represents the number 491.

The root-to-leaf path 4->0 represents the number 40.

Therefore, sum = 495 + 491 + 40 = 1026.

## Solution:

/**
* 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:

static constexpr const size_t npos = static_cast<size_t>(-1);

struct WayPoint{
size_t last;
TreeNode *node;
};

unordered_map<size_t, WayPoint> wayPoints;

size_t AllocateWayPoint(){
size_t next = wayPoints.size();
wayPoints.insert(move(make_pair(next, WayPoint{})));
return next;
}

int sumNumbers(TreeNode* root) {
wayPoints.clear();

if(root == nullptr){
return 0;
}

vector<size_t> endPoints;

queue<size_t> myQueue;

while(!myQueue.empty()){
auto frontId = myQueue.front();
myQueue.pop();

const auto &front = wayPoints[frontId];

bool isLeaf = true;
if(front.node->left != nullptr){
isLeaf = false;
auto leftId = AllocateWayPoint();
wayPoints[leftId].last = frontId;
wayPoints[leftId].node = front.node->left;
myQueue.push(leftId);
}
if(front.node->right != nullptr){
isLeaf = false;
auto rightId = AllocateWayPoint();
wayPoints[rightId].last = frontId;
wayPoints[rightId].node = front.node->right;
myQueue.push(rightId);
}

if(isLeaf){
endPoints.push_back(frontId);
}

}

int allSum = 0;
for(auto point : endPoints){
int times = 1;
while(point != npos){
allSum += wayPoints[point].node->val * times;
times *= 10;
point = wayPoints[point].last;
}
}

return allSum;
}
};


Traverse the binary tree to find all leaf nodes, and then find a path from that leaf node to the root.