题目：

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1

return

[   [5,4,11,2],   [5,8,4,5]]

解题思路：

简单的DFS。

代码：

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 11 class Solution {12 public:13     int vec_sum(vector
     
       &cur_ans) {14         int sum = 0;15         for (int i = 0; i < cur_ans.size(); i++) {16             sum += cur_ans[i];17         }18         return sum;19     }20     void search_dfs(TreeNode *root, vector
      
        &cur_ans, int sum, vector
       
        
         > &ans) {21         if (root->left == NULL && root->right == NULL) {22             cur_ans.push_back(root->val);23             if (vec_sum(cur_ans) == sum) ans.push_back(cur_ans);24             cur_ans.pop_back();25         }26         else {27             cur_ans.push_back(root->val);28             if (root->left != NULL) search_dfs(root->left, cur_ans, sum, ans);29             if (root->right != NULL) search_dfs(root->right, cur_ans, sum, ans);30             cur_ans.pop_back();31         }32         return;33     }34     vector
         
          
            > pathSum(TreeNode *root, int sum) {35 vector
           
            
             > ans;36 if (root == NULL) return ans;37 38 vector
             
               cur_ans;39 40 search_dfs(root, cur_ans, sum, ans);41 return ans;42 }43 };