Leetcode 437. 路径总和 III

题目

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

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

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

二叉树不超过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

题解

采用先序遍历的思想，我们记录从根节点到第level层的路径的和，然后遍历查看是否存在一条自上而下的路径其和为sum。详细过程见代码

代码

unordered_map<int,int> curSum;
    int ans;
    void search(TreeNode* root,int sum,int level){
        if(root == NULL)    return;
        curSum[level] = curSum[level-1] + root->val;
        for(int i=-1; i<level; i++)			//第i+1层作为起点，本节点作为终点，判断路径和是不是sum
            if(curSum[level] - curSum[i] == sum)    ans++;
        search(root->left,sum,level+1);
        search(root->right,sum,level+1); 
    }
    int pathSum(TreeNode* root, int sum) {
        curSum[-1] = 0;		//保证根节点会作为起点
        search(root,sum,0);
        return ans;
    }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。