Similar to #112 and #113, check the whole tree.
The only difference is: Any node can play as start or end in a valid path.
After each visit, use current node as start, and update the "targets" list.
Pass the updated targets and initial target through.
- node is None
- node fits in certain path sum.
- node doesn't meet.
class Solution(object): def pathSum(self, root, s): return self.helper(root, s, [s]) def helper(self, node, origin, targets): if not node: return 0 hit = 0 for t in targets: if not t-node.val: hit += 1 # count if sum == target targets = [t-node.val for t in targets]+[origin] # update the targets return hit+self.helper(node.left, origin, targets)+self.helper(node.right, origin, targets)
@YJL1228 what does tgts mean?
I hope you can write your code longer.
it would be much more readable.
@Zura Thanks for your reply. The variable "tgts" is renamed into "targets", and I hope it would be easier to understand. The basic idea is keep update targets (distance to sum) when new nodes are met, and count one when sum is reached.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.