解法一:(深度优先搜索)穷举所有的可能 =》访问每一个节点 node,检测以 node 为起始节点且向下延深的路径有多少种。递归遍历每一个节点的所有可能的路径,然后将这些路径数目加起来即为返回结果。
class Solution {
public int pathSum(TreeNode root, int targetSum) {
if(root==null){
return 0;
}
int res = rootSum(root, targetSum);
res += pathSum(root.left, targetSum);
res += pathSum(root.right, targetSum);
return res;
}
public int rootSum(TreeNode root, int targetSum){
if(root==null){
return 0;
}
int res = 0;
if(root.val==targetSum){
res++;
}
res += rootSum(root.left, targetSum-root.val);
res += rootSum(root.right, targetSum-root.val);
return res;
}
}
注意:
public int pathSum(TreeNode root, int targetSum)
:根节点+左节点+右节点分开单独遍历每一个节点的所有可能的路径;public int rootSum(TreeNode root, int targetSum)
遍历根节点所有可能的路径。- 将
pathSum(TreeNode root, int targetSum)
和rootSum(TreeNode root, int targetSum)
的int
改为long
可以解决下述问题。
