[LeetCode] 437. Path Sum III #437

grandyang · 2019-05-30T16:21:14Z

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

**Input:** root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
**Output:** 3
**Explanation:** The paths that sum to 8 are shown.

Example 2:

**Input:** root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
**Output:** 3

Constraints:

The number of nodes in the tree is in the range [0, 1000].
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000

这道题让我们求二叉树的路径的和等于一个给定值，说明了这条路径不必要从根节点开始，可以是中间的任意一段，而且二叉树的节点值也是有正有负。那么可以用递归来做，相当于先序遍历二叉树，对于每一个节点都有记录了一条从根节点到当前节点到路径，同时用一个变量 curSum 记录路径节点总和，然后看 curSum 和 sum 是否相等，相等的话结果 res 加1，不等的话继续查看子路径和有没有满足题意的，做法就是每次去掉一个节点，看路径和是否等于给定值，注意最后必须留一个节点，不能全去掉了，因为如果全去掉了，路径之和为0，而如果给定值刚好为0的话就会有问题，整体来说不算一道很难的题，参见代码如下：

解法一：

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        int res = 0;
        vector<TreeNode*> out;
        helper(root, targetSum, 0, out, res);
        return res;
    }
    void helper(TreeNode* node, int targetSum, long curSum, vector<TreeNode*>& out, int& res) {
        if (!node) return;
        curSum += node->val;
        out.push_back(node);
        if (curSum == targetSum) ++res;
        long t = curSum;
        for (int i = 0; i < out.size() - 1; ++i) {
            t -= out[i]->val;
            if (t == targetSum) ++res;
        }
        helper(node->left, targetSum, curSum, out, res);
        helper(node->right, targetSum, curSum, out, res);
        out.pop_back();
    }
};

我们还可以对上面的方法进行一些优化，来去掉一些不必要的计算，可以用 HashMap 来建立路径之和跟其个数之间的映射，即路径之和为 curSum 的个数为 m[curSum]，这里需要将 m[0] 初始化为1，后面会讲解原因。在递归函数中，首先判空，若为空，直接返回0。然后就是 curSum 加上当前结点值。由于此时 curSum 可能已经大于了目标值 sum，所以用 curSum 减去 sum，并去 HashMap 中查找这个差值的映射值，若映射值大于0的化，说明存在结束点为当前结点且和为 sum 的路径，这就相当于累加和数组快速求某个区域和的原理。当 curSum 等于 sum 的时候，表明从根结点到当前结点正好是一条符合要求的路径，此时 res 应该大于0，这就是为啥要初始化 m[0] 为1的原因，举个例子来说吧，看下面这棵树：

假设 sum=3，当遍历根结点1时，curSum 为1，那么 curSum-sum=-2，映射值为0，然后建立映射 m[1]=1。此时遍历结点2，curSum 为3，那么 curSum-sum=0，由于 m[0] 初始化为1，所以 res=1，这是 make sense 的，因为存在和为3的路径。此时再遍历到第二个结点1，curSum 为4，那么 curSum-sum=1，由于之前建立了 m[1]=1 的映射，所以当前的 res 也为1，因为存在以第二个结点1为结尾且和为3的路径，那么递归返回到结点2时候，此时的 res 累加到了2，再返回根结点1时，res 就是2，最终就返回了2，那么可以看出递归函数的意义，某个结点的递归函数的返回值就是该结点上方或下方所有和为 sum 的路径总个数，参见代码如下：

解法二：

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long, int> m;
        m[0] = 1;
        return helper(root, (long)targetSum, 0, m);
    }
    int helper(TreeNode* node, long targetSum, long curSum, unordered_map<long, int>& m) {
        if (!node) return 0;
        curSum += node->val;
        int res = m[curSum - targetSum];
        ++m[curSum];
        res += helper(node->left, targetSum, curSum, m) + helper(node->right, targetSum, curSum, m);
        --m[curSum];
        return res;
    }
};

下面这种方法非常的简洁，用了两个递归函数，其中的一个 sumUp 递归函数是以当前结点为起点，和为 sum 的路径个数，采用了前序遍历，对于每个遍历到的节点进行处理，维护一个变量 pre 来记录之前路径之和，然后 cur 为 pre 加上当前节点值，如果 cur 等于 sum，那么返回结果时要加1，然后对当前节点的左右子节点调用递归函数求解，这是 sumUp 递归函数。而在 pathSum 函数中，我们对当前结点调用 sumUp 函数，加上对左右子结点调用 pathSum 递归函数，三者的返回值相加就是所求，参见代码如下：

解法三：

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;
        return sumUp(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }
    int sumUp(TreeNode* node, long pre, int targetSum) {
        if (!node) return 0;
        long cur = pre + node->val;
        return (cur == targetSum) + sumUp(node->left, cur, targetSum) + sumUp(node->right, cur, targetSum);
    }
};

Github 同步地址：

#437

类似题目：

Binary Tree Maximum Path Sum

Longest Univalue Path

参考资料：

https://leetcode.com/problems/path-sum-iii/

https://leetcode.com/problems/path-sum-iii/discuss/91889/Simple-Java-DFS