Path Sum II

TreeDFS
https://leetcode.com/problems/path-sum-ii

# 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
1
2
3
4
5

# Solution

Let nn be the number of nodes in the tree.

# DFS

Complexity

time: O(n)O(n)
space: O(n)O(n)

def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
    res = []

    def dfs(node: TreeNode, csum: int, path: List[int]):
        if not node:
            return

        csum += node.val
        if not node.left and not node.right and csum == targetSum:
            res.append(path[:] + [node.val])
            return

        path.append(node.val)
        dfs(node.left, csum, path)
        dfs(node.right, csum, path)
        path.pop()

    dfs(root, 0, [])
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19