算法
就是使用dfs,沿节点向下依次减值,注意,因为可能存在某一个路径是不合适的,因此回溯的时候,path需要之前放入的元素pop出来。恢复现场。
时间复杂度
参考文献
C++ 代码
int sum ;
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> findPath(TreeNode* root, int sum) {
sum = sum;
dfs(root, sum);
return res;
}
void dfs(TreeNode *root, int sum) {
if(!root) return;
path.push_back(root->val);
sum = sum - root->val;
if(!root->left && !root->right && !sum) res.push_back(path);
//上面判断过了,所以不需要再额外判断
dfs(root->left, sum);
dfs(root->right, sum);
path.pop_back();//恢复现场,那些不符合,回退的需要清理出去,不然就有可能加在正确的path里
}