题目描述
从任意起点,找一条连续的路径,使得和为sum。
思路:
1.可以遍历每一条路径,在遍历的过程中,如果和为sum,那么res++
2.再依次删除这条路径之前加入的节点,如果和为sum,那么res ++。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
int res = 0;
vector<TreeNode*> out;
helper(root, sum, 0, out, res);
return res;
}
void helper(TreeNode* node, int sum, int curSum, vector<TreeNode*>&out, int &res) {
if (!node) return ;
curSum += node->val;
out.push_back(node);
if (sum == curSum) res ++;
int t = curSum;
for (int i = 0; i < out.size() - 1; i ++) {// out,保存的当前路径,依次去掉路径中的点。
t -= out[i]->val;
if (t == sum) res ++;
}
helper(node->left, sum, curSum, out, res);
helper(node->right, sum, curSum, out, res);
out.pop_back();
}
};
楼主你好,想请问你最后递归函数里面为什么 要
out.pop_back()