Easy Recursive Python 7 lines Solution


  • 9

    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.

    Base case:

    1. node is None

    Recursive case:

    1. node fits in certain path sum.
    2. 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)
    

  • 0

    @YJL1228 what does tgts mean?


  • 0

    @YJL1228
    I hope you can write your code longer.
    it would be much more readable.


  • 0

    @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.


  • 0
    I

    the time complexity is O(n^2) right? Please correct me if I am wrong.


  • 0
    H

    I think the core idea is to find all the possible solutions counted from the top to the current node. And the current_targets for current node are the pre_node_targets - pre_node.val.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.