LeetCode 129. Sum Root to Leaf Numbers
08 Aug 2018Description:
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;
auto head = AllocateWayPoint();
wayPoints[head].last = npos;
wayPoints[head].node = root;
queue<size_t> myQueue;
myQueue.push(head);
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.