113.-path-sum-ii.md

description
Back-tracking

113. Path Sum II

• Medium

• Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

  A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Analysis

This is a ordinary back-tracking problem.

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        ans=[]
        answer=[]
        self.helper(root,targetSum,ans,answer)
        return answer
        
        
    def helper(self,root,target,ans,answer):
        if not root:
            return 
        if target==root.val and not root.right and not root.left:
            answer.append(ans+[root.val])

        if root.left:
            self.helper(root.left,target-root.val,ans+[root.val],answer)
        if root.right:
            self.helper(root.right,target-root.val,ans+[root.val],answer)
        return