# Paths with Sum II

> You are given a binary tree in which each node contains an integer value (which might be positive or negative)

- 作者：[小土刀](https://wdxtub.com/about)
- 发布日期：2016-01-12
- 原文（引用请使用此链接）：https://wdxtub.com/blog/interview/paths-with-sum-ii
- 所属系列：interview 面试刷题笔记
- 标签：面试刷题、树和图
- 许可：CC BY-NC-SA 4.0（https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh）
- 正文中的站内图片路径以 https://wdxtub.com 为根目录。

> 阅读提示：这是 2016 年前后整理的历史面试资料。面经与招聘信息仅代表当时情况，代码包含旧语言版本及未完成笔记；练习时请自行验证边界条件和运行结果。

---

## Paths with Sum II

You are given a binary tree in which each node contains an integer value (which might be positive or negative). Design an algorithm to count 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)

### Solution

暂时只想到暴力法

### Code

```java
// Brute Force
int countPath(TreeNode root, int sum){
    if (root == null)
        return 0;

    int pathsRoot = countPathFromNode(root, sum, 0);

    int pathsLeft = countPath(root.left, sum);
    int pathsRight = countPath(root.right, sum);

    return pathsRoot + pathsLeft + pathsRight;
}

int countPathFromNode(TreeNode node, int sum, int curSum){
    if (node == null){
        return 0;
    }

    curSum += node.data;

    int totalPath = 0;
    if (curSum == sum){
        totalPath++;
    }

    totalPath += countPathFromNode(node.left, sum, curSum);
    totalPath += countPathFromNode(node.right, sum, curSum);

    return totalPath;
}
```

