/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int PathSum(TreeNode root, int sum)
{
if (root == null)
{
return ;
}
return PathSumFrom(root, sum) + PathSum(root.left, sum) + PathSum(root.right, sum);
} private int PathSumFrom(TreeNode node, int sum)
{
if (node == null)
{
return ;
}
return (node.val == sum ? : )
+ PathSumFrom(node.left, sum - node.val) + PathSumFrom(node.right, sum - node.val);
}
}
https://leetcode.com/problems/path-sum-iii/#/description
补充一个python实现，使用递归：
class Solution:
def pathSum(self, root: 'TreeNode', sum: 'int') -> 'int':
if root == None:
return
return self.pathSumWithRoot(root,sum) + self.pathSum(root.left,sum) + self.pathSum(root.right,sum) def pathSumWithRoot(self,root,sum):
if root == None:
return
ret =
if root.val == sum:
ret +=
ret += self.pathSumWithRoot(root.left,sum-root.val) + self.pathSumWithRoot(root.right,sum-root.val)
return ret
这种实现的时间复杂度是O(n^2)，执行效率比较低。
再补充一个更高效的实现，使用hash表进行缓存：（如果必须符合这个时间复杂度的要求O(n)，就可以当作hard级别的题目了）
class Solution(object):
def pathSum(self, root, target):
# define global result and path
self.result =
cache = {:} # recursive to get result
self.dfs(root, target, , cache) # return result
return self.result def dfs(self, root, target, currPathSum, cache):
# exit condition
if root is None:
return
# calculate currPathSum and required oldPathSum
currPathSum += root.val
oldPathSum = currPathSum - target
# update result and cache
self.result += cache.get(oldPathSum, )
cache[currPathSum] = cache.get(currPathSum, ) + # dfs breakdown
self.dfs(root.left, target, currPathSum, cache)
self.dfs(root.right, target, currPathSum, cache)
# when move to a different branch, the currPathSum is no longer available, hence remove one.
cache[currPathSum] -=
