Using preOrder traversal, record the length of all the path with hash_table when encounter leaf. We only need find whether the sum is in the hash_table after we find every single path.

class Solution {

public:

```
bool hasPathSum(TreeNode* root, int sum) {
int path = 0;
unordered_set<int> result;
PathSum(root, path, result);
if (result.find(sum) == result.end()) {
return false;
}
return true;
}
void PathSum(TreeNode* root, int path, unordered_set<int>& result) {
if (root != NULL) {
path += root->val;
PathSum(root->left, path, result);
PathSum(root->right, path, result);
if (root->left == NULL && root->right == NULL) {
result.insert(path);
} // insert in to hashtable when encountered leaf.
}
}
```

};