leetcode 113、路径总和II

老规矩先看题目：
题解：
题目中从根节点到叶子结点不难想到搜索界的大哥--深度优先搜索，
方法：枚举所有路径，去判断符合条件吗？
/** * Definition for a binary tree node. * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode() : val(0), left(nullptr), right(nullptr) {} *TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:vector> sov;vectorpath;void dfs(TreeNode *p,int targetSum){if(p==nullptr) return;path.push_back(p->val);targetSum-=p->val;if(p->left==nullptr&&p->right==nullptr&&targetSum==0){sov.push_back(path);}dfs(p->left,targetSum);dfs(p->right,targetSum);path.pop_back();}vector> pathSum(TreeNode* root, int targetSum) {dfs(root,targetSum);return sov;}};
记住现在的运行时间！
【leetcode 113、路径总和II】下面进行回溯
class Solution {public:vector> sov;vectorpath;void dfs(TreeNode *p,int targetSum,int sum){if(p==nullptr) return;sum+=p->val;path.push_back(p->val);if(!p->left&& !p->right && sum==targetSum){sov.push_back(path);path.pop_back();return;}dfs(p->left,targetSum,sum);dfs(p->right,targetSum,sum);path.pop_back();}vector> pathSum(TreeNode* root, int targetSum) {dfs(root,targetSum,0);return sov;}}; 再来看看时间
哈哈！时间一下变为了4ms 。
在到达叶子结点并判断是否是题目所给的数targetsum ，我让他直接返回，不过在此之前必须加上pop——back（）函数。
小白的解释：其实上面的枚举法和下面的回溯法，在本质上是一样的，因为递归就有回溯的效果。
不对，勿喷！