Leetcode 113. Path Sum II (Python)

Related Topic

Depth-First-Search. Tree.

Description

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Sample I/O

Example 1

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return 

[
   [5,4,11,2],
   [5,8,4,5]
]

Note

A leaf is a node with no children.

Methodology

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.

Code(DFS)

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

BigO

We traversal all nodes of the tree once so O(n) and we need to append each root value to the answer which takes O(n) so total is O(n^2)