2014.1.8 05:38

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

Solution:

　　This problem is a variation from . The difference is that you need to find out all the paths, instead of just judging the existence of these paths.

　　To hold the result, extra arrays are needed. Also there needs to be one array passed as parameter, so as to record path during the recursion.

　　Time and space complexities are both O(n), where n is the number of nodes in the tree.

Accepted code:

1 // 1RE, 1AC 2 /** 3  * Definition for binary tree 4  * struct TreeNode { 5  *     int val; 6  *     TreeNode *left; 7  *     TreeNode *right; 8  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 9  * };10  */11 class Solution {12 public:13     vector
     
      
       > pathSum(TreeNode *root, int sum) {14         // IMPORTANT: Please reset any member data you declared, as15         // the same Solution instance will be reused for each test case.16         int i, n;17         n = result.size();18         for(i = 0; i < n; ++i){19             result[i].clear();20         }21         result.clear();22         arr.clear();23         if(root == nullptr){24             return result;25         }26         // 1RE here, forgot to push into $arr27         arr.push_back(root->val);28         dfs(root, root->val, sum);29         arr.pop_back();30         31         return result;32     }33 private:34     vector
       
        
         > result;35     vector
         
           arr;36     37     void dfs(TreeNode *root, int sum, int target){38         if(root == nullptr){39             return;40         }41         42         if(root->left == nullptr && root->right == nullptr){43             if(sum == target){44                 result.push_back(arr);45             }46             return;47         }48         49         if(root->left != nullptr){50             arr.push_back(root->left->val);51             dfs(root->left, sum + root->left->val, target);52             arr.pop_back();53         }54         if(root->right != nullptr){55             arr.push_back(root->right->val);56             dfs(root->right, sum + root->right->val, target);57             arr.pop_back();58         }59     }60 };