Leetcode 113 Path Sum II

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.

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Input: root = [1,2,3], targetSum = 5
Output: []

• This question can be solved by Depth First Search. Similar with question 112. Path Sum II and 257. Binary Tree Paths However, this time need to list all path that sum to the given sum

• We use dfs to traversal the tree. Each time we compare the sum and the current root value if the they are same and the root does not have left child and right child (root is leaf), then we find a path that equal to give sum, we need to return the the current root value and add to it’s previous path. Otherwist, we make the sum equal to sum - root.val and continue recursively find the next root.

# 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: TreeNode, sum: int) -> List[List[int]]:
            if not root:
                return []
            if not root.left and not root.right and sum == root.val:
                return [[root.val]]
            l_path = self.pathSum(root.left, sum-root.val)
            r_path = self.pathSum(root.right, sum-root.val)
            left = [[root.val]+l for l in l_path]
            right = [[root.val]+r for r in r_path]
            return left+right