二叉树路径总和III【递归】

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

  10<br />     /  \<br />    5   -3<br />   / \    \<br />  3   2   11<br /> / \   \<br />3  -2   1

返回 3。和等于 8 的路径有:

1. 5 -> 3
   2. 5 -> 2 -> 1
   3. -3 -> 11

解题思路： 双重递归，第一从递归是以(每一个父节点)根节点开始(子树)树搜索满足条件的路径，搜索里面采用递归的深度优先搜索方式进行。

代码：

/**
 * 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 {
    int ans = 0;
public:
    void subPathSum(TreeNode * node, int sum)
    {
        if (node->val == sum)
            ans++;
        if (node->left != NULL)
            subPathSum(node->left, sum - node->val);
        if (node->right != NULL)
            subPathSum(node->right, sum - node->val);
    }
    // 双重递归
    int pathSum(TreeNode* root, int sum) {
        if (root == NULL)
            return 0;
        subPathSum(root, sum);
        pathSum(root->left, sum);
        pathSum(root->right, sum);
        return ans;
    }
};

解题思路二：双重递归中包含太多的重复计算，而且递归深度太深，比较吃内存； 在和为K的子数组个数中笔者介绍采用前缀和prefix_sum的hash_table统计子数组个数； 这里也可以采用同样的方式：问题转换为和为sum的(连续某一路径)子树个数；从所有根节点到叶子结点组成的数组中所有和为K的子数组个数；

示意图如下：

即：统计4条路径的和为k的子数组的个数；

// hash_map: prefix-sum
class Solution {
public:
    // 存储当前路径前缀中和prefix_sum为key, 其出现次数为value的hash_map
    unordered_map<int, int> prefixSum_map;

    int subPathSum(TreeNode * root, int sum, int prefix_sum){
        if (!root)
            return 0;
        int res = 0;
        // 当前路径结点前缀和
        prefix_sum += root->val;
        // 如果当前路径中存在prefix_sum - sum的值
        res += prefixSum_map[prefix_sum - sum];
        // 在hash_map中添加前缀和出现次数
        prefixSum_map[prefix_sum]++;
        // 递归子树中路径
        res += subPathSum(root->left, sum, prefix_sum) + subPathSum(root->right, sum, prefix_sum);
        // 移除不在该路径上的prefix_sum一次; 防止被其他路径复用
        prefixSum_map[prefix_sum]--;
        return res;
    }

    int pathSum(TreeNode* root, int sum) {
        prefixSum_map[0] = 1;
        return subPathSum(root, sum, 0);
    }
};

欢迎点评！