题目描述
You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
backtracking解题思路
- 类似于剑指offer，路径和检查每条叶子路径是否是指定的值
- 这一题是该题的变形，路径可以不是叶子节点，即中间的某一段路径
- 用一个临时变量来存储，每次弹出一个，看是否等于指定的cur
- 如果是，就累加。
/**
* 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;
int cur = 0;
vector<TreeNode*> path;
if(root != NULL){
fun_helper(root, sum, cur, res, path);
}
return res;
}
void fun_helper(TreeNode* root, int sum ,int cur, int& res, vector<TreeNode*>& path){
if(root == NULL){
return ;
}
cur += root -> val;
path.push_back(root);
if(cur == sum){
res++;
}
int t = cur;
for(int i = 0; i < path.size() - 1; i++){ // 最后一个节点不能算
t -= path[i] -> val;
if(t == sum){
res++;
}
}
fun_helper(root -> left, sum, cur, res, path);
fun_helper(root -> right, sum, cur, res, path);
path.pop_back();
}
};
第二遍刷题
/**
* 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;
int cur = 0;
vector<TreeNode*> path;
if(root != NULL){
fun_helper(root, sum, cur, res, path);
}
return res;
}
void fun_helper(TreeNode* root, int sum ,int cur, int& res, vector<TreeNode*>& path){
cur += root -> val;
path.push_back(root);
if(cur == sum){
res++;
}
int t = cur;
for(int i = 0; i < path.size() - 1; i++){ // 把root之前的节点 都给遍历一遍，从0到没有push(root)节点之前
t -= path[i] -> val;
if(t == sum){
res++;
}
}
if(root -> left){
fun_helper(root -> left, sum, cur, res, path); // 这个cur是一直增加的 所以前面需要遍历path路径，做减法，来判断是否相等
}
if(root -> right){
fun_helper(root -> right, sum, cur, res, path);
}
path.pop_back();
}
};
第三遍刷题
/**
* 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:
int pathSum(TreeNode* root, int sum) {
if(root == nullptr){
return 0;
}
int res = 0;
dfs(root, 0, sum, res, {});
return res;
}
void dfs(TreeNode* root, int cur, int sum, int& res, vector<TreeNode*> path){
if(root == nullptr){
return;
}
cur += root -> val;
path.push_back(root);
if(cur == sum){
res++;
}
int t = cur;
for(int i = 0; i < path.size() - 1; i++){
t -= path[i] -> val;
if(t == sum){
res++;
}
}
dfs(root -> left, cur, sum, res, path);
dfs(root -> right, cur, sum, res, path);
path.pop_back();
}
};
