带明显的回溯的版本
#include <vector>
using std::vector;
class Solution {
private:
vector<int> res;
int sum = 0;
public:
void cnt_sum(TreeNode *root) {
if (root->left == nullptr && root->right == nullptr) {
sum += root->val;
res.push_back(sum);
return;
}
sum += root->val;
if (root->left != nullptr) {
cnt_sum(root->left);
sum -= root->left->val;//回溯
}
if (root->right != nullptr) {
cnt_sum(root->right);
sum -= root->right->val;//回溯
}
return;
}
bool hasPathSum(TreeNode *root, int targetSum) {
if (root == nullptr)
return false;
cnt_sum(root);
for (int i : res) {
if (i == targetSum)
return true;
}
return false;
}
};
回溯被隐藏起来的版本
#include <vector>
using std::vector;
class Solution {
private:
vector<int> res;
//int sum = 0;
public:
void cnt_sum(TreeNode *root, int sum) {
if (root->left == nullptr && root->right == nullptr) {
sum += root->val;
res.push_back(sum);
return;
}
sum += root->val;
if (root->left != nullptr) {
cnt_sum(root->left, sum); //注意这里的sum作为实参,其值被改变并不会改变实际上sum的值
//sum -= root->left->val;
}
if (root->right != nullptr) {
cnt_sum(root->right, sum);
//sum -= root->right->val;
}
return;
}
bool hasPathSum(TreeNode *root, int targetSum) {
if (root == nullptr)
return false;
cnt_sum(root, 0);
for (int i = 0; i < res.size(); i++)
if (res[i] == targetSum)
return true;
return false;
}
};
标签:cnt,right,return,sum,nullptr,112,path,root
From: https://www.cnblogs.com/zwyyy456/p/16647641.html