Path Sum[LeetCode]

Problem Description:  http://oj.leetcode.com/problems/path-sum/
Pretty.

 1 /**

 2  * Definition for binary tree

 3  * struct TreeNode {

 4  *     int val;

 5  *     TreeNode *left;

 6  *     TreeNode *right;

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

 8  * };

 9  */

10 class Solution {

11 public:

12     vector<int> getSums(TreeNode *root) {

13         vector<int> sums;

14 

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

16             sums.push_back(root->val);

17             

18         if(root->left != NULL){

19             vector<int> left_sums;

20             left_sums = getSums(root->left);

21             for(auto item : left_sums) {

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

23             }

24         }

25         

26         if(root -> right != NULL) {

27             vector<int> tmp_sums;

28             tmp_sums = getSums(root->right);

29             for(auto item : tmp_sums) {

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

31             }

32         }

33         

34         return sums;

35     }

36     

37     bool hasPathSum(TreeNode *root, int sum) {

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

39         if(root == NULL)

40             return false;

41         

42         vector<int> sums = getSums(root);

43         

44         for(auto item : sums) {

45             if(item == sum)

46                 return true;

47         }

48         

49         return false;

50     }

51 };