# 437.Path Sum III

**437.Path Sum III**

难度:Easy

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

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

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

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

示例：

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

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
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 {
private:
    int res=0;
    void getsum(TreeNode* root, int sum)
    {
        if(!root) return ;
        sum-=root->val;
        if(sum==0) res++;
        getsum(root->left,sum);
        getsum(root->right,sum);
    }
public:
    int pathSum(TreeNode* root, int sum) {
        
        if(!root) return 0;
        getsum(root,sum);
        pathSum(root->left,sum);
        pathSum(root->right,sum);
        return res;
    
    

       
    }
};
```

> 执行用时 : 28 ms, 在Path Sum III的C++提交中击败了97.19% 的用户\
> 内存消耗 : 14.8 MB, 在Path Sum III的C++提交中击败了77.24% 的用户


---

# 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://dfine.gitbook.io/leetcode/437.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.