# C++ recursion with a hash table: clumsy but easy to understand, 20ms

• First idea:
Here we need to record the parent node and the original value.
Ideally, in some language supporting dynamic properties, we can attach the parent and old value to each node. However, this is not supported in c++.
A workaround is to use a hash table to map each node --> parent and old value.

``````class Solution {
std::unordered_map<TreeNode*, std::pair<TreeNode*, int>> map; // for each node p, record the parent node and p's value
std::vector<TreeNode*> qualifiedLeaves;
// find the leaf nodes whose path sum is the given one
void findQualifiedLeaves(TreeNode* root, int sum){
if (root == nullptr)
return;
if (root->left == nullptr && root->right == nullptr){ // a leaf node
if (root->val == sum)
qualifiedLeaves.push_back(root);
}
if (root->left != nullptr){
map.emplace(root->left, std::make_pair(root, root->left->val));
root->left->val += root->val;
findQualifiedLeaves(root->left, sum);
}
if (root->right != nullptr){
map.emplace(root->right, std::make_pair(root, root->right->val));
root->right->val += root->val;
findQualifiedLeaves(root->right, sum);
}
}

public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
std::vector<std::vector<int>> paths;
if (root == nullptr)
return paths;
map.emplace(root, std::make_pair(nullptr, root->val));
findQualifiedLeaves(root, sum);

for (auto p: qualifiedLeaves){// for each qualified leaf, we track back to the root
std::vector<int> path;
TreeNode* parent = nullptr;
int val = 0;
while (p != nullptr){ // backtracking
std::tie(parent, val) = map[p];
path.push_back(val);
p = parent;
}
std::reverse(path.begin(), path.end());
paths.emplace_back(std::move(path));
}
return paths;

}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.