leetcode 链接：求和路径
《程序员面试代码指南》by 左程云中相似题目：★★☆☆在二叉树中找到累加和为指定值的最长路径长度

题目

给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。

示例：
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

3
解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]

解答

方法一：

参考：《程序员面试代码指南》by 左程云中相似题目：★★☆☆在二叉树中找到累加和为指定值的最长路径长度

初始：
- 建立一个哈希表 sumMap，存储 <sum, cnt> 键值对，sum 代表从根节点到某个节点的和，cnt 代表从根节点到后续节点和为 sum 的节点数（也就是从根结点出发得到和为 sum 的节点数）
  - 初始存入 (0,1)
- preSum 代表从根节点到上一个节点（当前节点的父节点）的和，初始设为 0
- pathCnt 代表和为目标值的路径数，即答案，初始设为 0

递归，前序遍历 void preOrder(TreeNode* root, int preSum, int targetSum, int& pathCnt, unordered_map<int, int> sumMap)

递归结束条件：
- root 为空，返回
将 preSum 和 root 的值相加，得到从二叉树根节点到当前节点 root 的和 curSum
在哈希表中查找 curSum - targetSum
- 如果存在，则将路径数 + 哈希表中其对应的键值
如果哈希表中存在 curSum，则将其键值 + 1；否则插入 (curSum, 1)
递归左子树
递归右子树

回溯：将刚才在哈希表中增加的 curSum 键值 -1，变回原样，如果减为 0 ，删掉该记录

/**
* 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 {
private:
void preOrder(TreeNode* root, int preSum, int targetSum, int& pathCnt, unordered_map<int, int> sumMap)
{
   if(root == NULL)
       return;

   int curSum = preSum + root->val;
   if(sumMap.find(curSum - targetSum) != sumMap.end())
       pathCnt += sumMap[curSum-targetSum];

   if(sumMap.find(curSum) == sumMap.end())
       sumMap.insert(make_pair(curSum, 1));
   else
       sumMap[curSum] += 1;

   preOrder(root->left, curSum, targetSum, pathCnt, sumMap);
   preOrder(root->right, curSum, targetSum, pathCnt, sumMap);

   sumMap[curSum] -= 1;
   if(sumMap[curSum] == 0)
       sumMap.erase(curSum);
}
public:
int pathSum(TreeNode* root, int sum) {
   unordered_map<int, int> sumMap;
   sumMap.insert(make_pair(0, 1));

   int preSum = 0;
   int pathCnt = 0;
   preOrder(root, preSum, sum, pathCnt, sumMap);
   return pathCnt;
}
};

执行结果： ``` 执行结果：通过

执行用时：460 ms, 在所有 C++ 提交中击败了 5.55% 的用户内存消耗：96.3 MB, 在所有 C++ 提交中击败了 5.10% 的用户

<a name="MKriF"></a>
## 方法二：
先调用 `void preOrder(TreeNode* root, int sum, int& pathCnt)` 这个函数深度优先遍历二叉树的每个节点：

- 递归结束条件，如果当前节点为空，则返回
- 调用 `calPathCnt(TreeNode* root, int target, int& pathCnt)` 计算以当前节点为根节点的子树中路径和为 `sum` 的路径数
- 递归遍历左子树
- 递归遍历右子树
```cpp
/**
 * 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 {
private:
    void calPathCnt(TreeNode* root, int target, int& pathCnt)
    {
        if(root == NULL)
            return;

        target -= root->val;    // target 是从根节点走到当前节点的这条路径上，目标 sum 减去这条路径上各结点的值的差
        if(target == 0)    // 如果 target 减为 0，说明这条路径的节点值和为目标 sum
            ++pathCnt;    // 路径数 +1

        calPathCnt(root->left, target, pathCnt);
        calPathCnt(root->right, target, pathCnt);
    }
    void preOrder(TreeNode* root, int sum, int& pathCnt)
    {
        if(root == NULL)
            return;

        calPathCnt(root, sum, pathCnt);

        preOrder(root->left, sum, pathCnt);
        preOrder(root->right, sum, pathCnt);
    }
public:
    int pathSum(TreeNode* root, int sum) {
        int pathCnt = 0;
        preOrder(root, sum, pathCnt);
        return pathCnt;
    }
};

执行结果：

执行结果：通过

执行用时：20 ms, 在所有 C++ 提交中击败了 41.17% 的用户
内存消耗：18.6 MB, 在所有 C++ 提交中击败了 74.76% 的用户

《程序员面试金典（第 6 版）》

[中等] 4.12 求和路径

题目

解答

方法一：