​437. 路径总和 III​

1、题目描述

2、题目分析

通过题目可以得到下来3个条件：

1、求路径数目：一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

2、路径 不需要从根节点开始，也不需要在叶子节点结束

3、要求 路径方向必须是向下的（只能从父节点到子节点）

具体代码实现如下：

class Solution {
    int sumPath = 0;
    public int pathSum(TreeNode root, long targetSum) {
        if(root == null) return 0;
        sumValue(root,0,targetSum);

        //左右子树中任何节点都有成为出发点的可能，因此分别递归
        pathSum(root.left,targetSum);
        pathSum(root.right,targetSum);

        return sumPath;     
    }

    private void sumValue(TreeNode root, long sum, long targetSum){
        if(root == null) return ;
        
        sum += root.val;
        if(sum == targetSum){
             sumPath++;
        }
        //左右子树分别遍历
        sumValue(root.left, sum, targetSum);
        sumValue(root.right, sum, targetSum);
    }
}

复杂度分析

时间复杂度：O(N^2)，其中 N为该二叉树节点的个数。对于每一个节点，求以该节点为起点的路径数目时，则需要遍历以该节点为根节点的子树的所有节点，因此求该路径所花费的最大时间为 O(N)，我们会对每个节点都求一次以该节点为起点的路径数目，因此时间复杂度为O(N^2)。

空间复杂度：O(N)，考虑到递归需要在栈上开辟空间。

代码中需要注意的点：

1、 //左右子树中任何节点都有成为出发点的可能，因此分别递归
        pathSum(root.left,targetSum);
        pathSum(root.right,targetSum);

2、在编译时，倒数第二个case编译不过[1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000]  0

       原因是数字范围超过int的范围，因此编译出错。

       修改完善条件，如上面代码所示，把【目标和】和中间步骤的【累积加】全部由int变成long型。 既 long sum, long targetSum。