# 437. Path Sum III

> You are given a binary tree in which each node contains an integer value.
>
> Find the number of paths that sum to a given value.
>
> The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
>
> The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

## Thoughts

先用分治思想，path所在分为三种情况: path初始点在左子树，右子树或从当前结点初始。\
trick在从当前结点初始时相当于又是一个分治思想，是求对node.left/right的sum-node.val。

## Code

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int count = 0;
    private int findPaths(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }

        int res = 0;
        if (node.val == sum) {
            res++;
        }

        res += findPaths(node.left, sum - node.val);
        res += findPaths(node.right, sum - node.val);

        return res;
    }


    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }

        return findPaths(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
}
```

## Analysis

两重分治，内外分别都是对树遍历, 时间复杂度O(n^2)。

## Ver.2

<https://leetcode.com/problems/path-sum-iii/discuss/91878/>

preSum思想, 把树看作多条path的array. 利用hash map存储当前path的presum，存在则意味着presum\[psum - cur] != null。多个path之间不能弄混了，所以当backtracking结束后要把该结点从path中移除，同时把preSum中相应的sum的频率减一.。注意preSum需要初始化0，用来cover root到当前点的sum刚好等于target的情况。

```java
public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> preSum = new HashMap();
        preSum.put(0,1);
        return helper(root, 0, sum, preSum);
    }

    public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
        if (root == null) {
            return 0;
        }

        currSum += root.val;
        int res = preSum.getOrDefault(currSum - target, 0);
        preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);

        res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);
        preSum.put(currSum, preSum.get(currSum) - 1);
        return res;
    }
```

## Ver.3

改写成iterative需要注意++presum不能在计算target sum是否存在的前面，因为当target == 0时，我们相当于在问是否存在到cur和为psum的路径，那肯定是存在的。

```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 {
public:
    int pathSum(TreeNode* root, int sum) {
        if (root == NULL) return 0;
        stack<TreeNode*> s;
        int psum = 0;
        unordered_map<int, int> presum;
        presum[0] = 1;
        int res = 0;
        const auto push_left = [&](TreeNode *cur) {
            while (cur != NULL) {
                s.push(cur);
                psum += cur->val;
                cur = cur->left;
                // The order of the following two lines are important!
                if (presum.find(psum - sum) != presum.end()) res += presum[psum - sum]; 
                ++presum[psum];
            }
        };
        push_left(root);
        TreeNode *pre;
        while (!s.empty()) {
            const auto cur = s.top();
            if (cur->right != NULL && cur->right != pre) {
                push_left(cur->right);
                continue;
            }
            s.pop();
            pre = cur;
            --presum[psum];
            psum -= cur->val;
        }
        return res;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/path-sum/path-sum-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.