Path Sum II

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]]

 

 

采用深度优先搜索即可

 

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
      
       
         > pathSum(TreeNode *root, int sum) {13         vector
        
          tmp;14         vector
         
          
            > result;15         if(root==NULL)16         {17             return result;18         }19         DFS(root,sum,tmp,result);20         return result;21        22     }23    24     void DFS(TreeNode *root,int &sum, vector
           
             tmp,vector
            
             
               > &result,int cur=0)25 {26 if(root==NULL)27 {28 return;29 }30 31 int val=root->val;32 tmp.push_back(val);33 34 if(root->left==NULL&&root->right==NULL)35 {36 if(cur+val==sum) result.push_back(tmp);37 return;38 }39 DFS(root->left,sum,tmp,result,cur+val);40 DFS(root->right,sum,tmp,result,cur+val);41 }42 };