/**

  * Definition for binary tree

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

     vector<int> getSums(TreeNode *root) {

         vector<int> sums;

         if(root->left == NULL && root->right == NULL)

             sums.push_back(root->val);

         if(root->left != NULL){

             vector<int> left_sums;

             left_sums = getSums(root->left);

             for(auto item : left_sums) {

                 sums.push_back(item + root->val);

             }

         }

         if(root -> right != NULL) {

             vector<int> tmp_sums;

             tmp_sums = getSums(root->right);

             for(auto item : tmp_sums) {

                 sums.push_back(item + root->val);

             }

         }

         return sums;

     }

     bool hasPathSum(TreeNode *root, int sum) {

         // Note: The Solution object is instantiated only once and is reused by each test case.

         if(root == NULL)

             return false;

         vector<int> sums = getSums(root);

         for(auto item : sums) {

             if(item == sum)

                 return true;

         }

         return false;

     }

 };