看大家的题解都是用了全局变量,这里贴一个没有使用全局变量的写法
如下: 当然如果路径过长而且很多的话,会慢下来,n^2的时间复杂度(主要是移动数据)
class Solution {
public:
vector<vector<int>> dfs(TreeNode* root, int& sum, int num)
{
vector<vector<int>> res;
if(!root)
return res;
vector<int> ans1;
ans1.push_back(root->val);
if(!root->left && !root->right && (num + root->val == sum))
{
res.push_back(ans1);
}
if(root->left)
{
auto lval = dfs(root->left,sum,num + root->val);
for(int i = 0; i < lval.size(); i ++)
{
vector<int> ans(ans1.begin(),ans1.end());
for(int j = 0; j < lval[i].size(); j ++)
{
ans.push_back(lval[i][j]);
}
res.push_back(ans);
}
}
if(root->right)
{
auto rval = dfs(root->right,sum,num + root->val);
for(int i = 0; i < rval.size(); i ++)
{
vector<int> ans(ans1.begin(),ans1.end());
for(int j = 0; j < rval[i].size(); j ++)
{
ans.push_back(rval[i][j]);
}
res.push_back(ans);
}
}
return res;
}
vector<vector<int>> findPath(TreeNode* root, int sum) {
return dfs(root,sum,0);
}
};