容易想到对每个结点进行讨论 将每个结点满足条件的路径和加起来即为最后的路径数量 在二叉树中调用每个结点最常用的就是递归

可以设计一个函数递归求得某个结点的路径数 再设计一个函数遍历所有结点 将各个结点的路径数加和获得目标答案

int rootSum(TreeNode*root,int targetSum)

if(root==NULL)return 0;

int cnt=0;

if(targetSum==root- >val)cnt++;

//遍历左右子树

cnt+=rootSum(root- >left,targetSum-root- >val );

cnt+=rootSum(root- right,targetSum-root- >val );

return cnt;

通过这个函数我们可以获得某个节点满足情况的路径数

现在我们再用另外一个函数遍历获取最终结果

int pathSum(TreeNode*root ,int targetSum)

if(root==NULL)return 0;

int ret=rootSum(root,targetSum);//根结点满足路径数

ret+=pathSum(root- >left,targetSum);//遍历左树获得总路径数

ret+=pathSum(root- >right,targetSum);//遍历右树获得总路径数

return ret;

明显可以看到这个算法进行了很多重复计算,时间复杂度为O(n*n),还有很大的优化空间,事实上可以用上一题的哈希表结合前缀和,将时间复杂度降到O(n),因为时间紧张,能力不足,下次再进行探究