requirements

Given the root node of the binary tree, root, and an integer target and targetSum, find all paths from the root node to the leaf node where the sum of paths is equal to the given targetSum.

A leaf node is a node that has no children.

Example 1:

Input: root = [13,4,7,2 5,4,8,11, null, null, null, 5, 1], targetSum = 22 output: [,4,11,2 [5], [5,8,4,5]]Copy the code

Example 2:

Input: root = [1,2,3], targetSum = 5 output: []Copy the code

Example 3:

Input: root = [1,2], targetSum = 0Copy the code

Tip:

  • The total number of nodes in the tree is in the range [0, 5000]
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

The core code

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) - >List[List[int]] :
        if not root:
            return []
        return self.find_sum(root,targetSum,[])
    
    def find_sum(self,tree,s,path) :
        ans = []
        if self.is_leaf(tree):
            if tree.val == s:
                ans.append([*path,tree.val])
        else:
            if tree.left:
                ans.extend(self.find_sum(tree.left,s-tree.val,[*path,tree.val]))
            if tree.right:
                ans.extend(self.find_sum(tree.right,s-tree.val,[*path,tree.val]))
        return ans
    
    def is_leaf(self,node) :
        return not node.left and not node.right
Copy the code

It is the same as the sum of paths above, except that a target value is added to this problem. We traverse from the root node down to the leaf node, mark the value along the way, and then compare it with the target value to see if it is consistent. The consistent value is added to the output.