sundeepblue
3/17/2014 - 3:28 PM

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

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

``````vector<vector<int>> pathSum(TreeNode *root, int sum) {
vector<vector<int> > res;
vector<int> path;
if(!root) return res;
//DFS(root, res, path, 0, sum);
DFS(root, res, path, sum);
return res;
}

// solution 1: works
/*
void DFS(TreeNode *root, vector<vector<int>> &res, vector<int> path, int cur_sum, int sum) {
//if(!root) return; // no need to have this line
if(!root->left && !root->right && cur_sum + root->val == sum) {
path.push_back(root->val);
res.push_back(path);
return;
}
path.push_back(root->val);
if(root->left) DFS(root->left, res, path, cur_sum + root->val, sum);
if(root->right) DFS(root->right, res, path, cur_sum + root->val, sum);
path.pop_back();
} */

void DFS(TreeNode *root, vector<vector<int>> &res, vector<int> path, int sum) { // note, cannot write &path
// if(!root) return; // note, if have this line, no need to check at NOTE1 and NOTE2
if(!root->left && !root->right && root->val == sum) {
path.push_back(root->val);
res.push_back(path);
return;
}
path.push_back(root->val);
if(root->left) DFS(root->left, res, path, sum - root->val);     // NOTE1
if(root->right) DFS(root->right, res, path, sum - root->val);   // NOTE2
path.pop_back();
}``````