路径总和 II——力扣113

题目描述


方案：深度优先搜索
解题思路：
用sum值减去当前访问的节点值，若当前节点为叶子节点且减完为0，则将当前路径加入总路径中，否则，依次遍历左右孩子，没有就从上一个节点为起点进行深度优先遍历（path.pop_back()）

class Solution {
public:vector<vector<int>> ret;vector<int> path;void dfs(TreeNode* root, int targetSum) {if(root==nullptr) {return ;}path.emplace_back(root->val);targetSum -= root->val;if(root->left == nullptr && root->right == nullptr && targetSum==0){ret.emplace_back(path);}dfs(root->left, targetSum);dfs(root->right, targetSum);path.pop_back();}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {dfs(root, targetSum);return ret;}
};