# 2021.10.18 force buckle - path sum III

It's too powerful 2022-01-15 01:41:56

Title Description ：

Given the root node of a binary tree root , And an integer targetSum , Find that the sum of the node values in the binary tree is equal to targetSum Of route Number of .

route You don't need to start at the root node , It doesn't need to end at the leaf node , But the path has to be down （ Only from parent node to child node ）.

Example 1： Method 1 ：

``````/**
* 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 ans = 0;
//vector<vector<int>> ans2;
//void dfs(TreeNode* cur, int targetSum, int states, vector<int> states2)
void dfs(TreeNode* cur, int targetSum, int states)
{
if (cur == nullptr) return;
states += cur->val;
//states2.push_back(cur->val);
if (states == targetSum)
{
ans++;
//ans2.push_back(states2);
}
//dfs(cur->left, targetSum, states, states2);
dfs(cur->left, targetSum, states);
//dfs(cur->right, targetSum, states, states2);
dfs(cur->right, targetSum, states);
states -= cur->val;
//states2.pop_back();
}
void recur(TreeNode* cur,int targetSum)
{
if (cur == nullptr) return;
vector<int> states2 = {};
//dfs(cur, targetSum, 0, states2);
dfs(cur, targetSum, 0);
recur(cur->left, targetSum);
recur(cur->right, targetSum);
}
int pathSum(TreeNode* root, int targetSum) {
recur(root, targetSum);
//for (int i = 0; i < ans2.size(); i++)
//{
// for (int j = 0; j < ans2[i].size(); j++)
// {
// cout << ans2[i][j] << " ";
// }cout << endl;
//}
return ans;
}
};``````

Classic title , Such a simple solution to violence can never be done , Take it out and solve it today . The comment section in the code stores each path that matches .

In the following paragraph , I habitually put if The sentence is put in states += cur->val Before , But this will result in subsequent traversal cur Left and right subtrees of , The same path will be judged twice .

`````` states += cur->val;
//states2.push_back(cur->val);
if (states == targetSum)
{
ans++;
//ans2.push_back(states2);
}``````

Method 2 ：

`````` class Solution {
public:
int ans = 0;
void recur(TreeNode* cur, int targetSum,int curpresum, unordered_map<int, int>& mappresum)
{
if (cur == nullptr) return;
curpresum += cur->val;
if (mappresum.count(curpresum - targetSum))
{
ans += mappresum[curpresum - targetSum];
}
mappresum[curpresum]++;
recur(cur->left, targetSum, curpresum, mappresum);
recur(cur->right, targetSum, curpresum, mappresum);
mappresum[curpresum]--;
curpresum -= cur->val;
}
int pathSum(TreeNode* root, int targetSum) {
unordered_map<int, int> mappresum;
mappresum++;
int curpresum = 0;
recur(root, targetSum, curpresum, mappresum);
return ans;
}
};``````

Use prefixes and , Every time I traverse , Record from the root node to the node cur And curpresum, Then find out whether there is a prefix of a node and in the hash table curpresum - targetsum, If there is a description, this node is connected to cur The sum of paths is targetsum.

Since there may be a path, the starting position is the root node , Lead to curpresume == targetsum, So before recursion, you need to add... To the hash table 0 This number .

Notice that I have a problem in the process of writing , In the code below , I would have mappresum[curpresum]++; On the if The statement before , But this will result in adding... To the hash table first curpresum This number , If targetSum yes 0 Words , It will miscalculate one more path .

in addition , I'll start with  ans += mappresum[curpresum - targetSum]; It has been written. ans++, However, the prefix and are curpresum - targetSum There may be many situations .

`````` curpresum += cur->val;
if (mappresum.count(curpresum - targetSum))
{
ans += mappresum[curpresum - targetSum];
}
mappresum[curpresum]++;``````

thank
Similar articles