Path Sum II

TypeTree
Difficulty
Medium
Last Reviewed12/23/2024

Problem Description

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 a list of the node values.

Example 1

Input: [5,4,8,11,null,13,4,7,2,null,null,5,1]

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

Explanation: In this binary tree, the sum of the paths that equal 22 are [5,4,11,2] and [5,8,4,5].

Solution Overview

Initial Approach

To solve the 'Path Sum II' problem, we can use depth-first search (DFS) to traverse the binary tree. During the traversal, we keep track of the current path and the current sum. When we reach a leaf node, we check if the current sum equals the target sum. If it does, we add the current path to the result. We continue this process recursively for the left and right child nodes.

Step by Step Solution

  1. Initialize an empty list to store the result paths.
  2. Implement a recursive DFS function that takes the current node, current path, current sum, target sum, and the result list as parameters.
  3. In the DFS function, if the current node is a leaf node, check if the current sum equals the target sum. If it does, add the current path to the result list.
  4. Recursively call the DFS function for the left and right child nodes, passing the updated path and sum.
  5. Return the result list containing all valid paths that sum up to the target sum.

Solution Code

1
2# Definition for a binary tree node.
3class TreeNode:
4    def __init__(self, val=0, left=None, right=None):
5        self.val = val
6        self.left = left
7        self.right = right
8
9class Solution:
10    def pathSum(self, root, sum):
11        if not root:
12            return []
13        res = []
14        self.dfs(root, sum, [], res)
15        return res
16
17    def dfs(self, node, target, path, res):
18        if not node:
19            return
20        path.append(node.val)
21        if not node.left and not node.right and target == node.val:
22            res.append(list(path))
23        self.dfs(node.left, target - node.val, path, res)
24        self.dfs(node.right, target - node.val, path, res)
25        path.pop()
26

Solution Walkthrough

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.

Step 1

1class Solution:
2    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
3        if not root:
4            return []
5        res = []
6        self.dfs(root, targetSum, [], res)
7        return res
8    
9    def dfs(self, node, target, path, res):
10        if not node:
11            return
12        path.append(node.val)
13        if not node.left and not node.right and node.val == target:
14            res.append(path[:])
15        self.dfs(node.left, target - node.val, path, res)
16        self.dfs(node.right, target - node.val, path, res)

Define a function pathSum that takes the root node of a binary tree and an integer targetSum. Initialize an empty result list. Implement a helper function dfs which performs a depth-first search. If the current node is None, return. Append the current node value to the path. If the current node is a leaf node and its value equals the remaining target sum, append the current path to the result list. Recur for the left and right child nodes with updated target sum and path. Return the result list at the end.

State:

Complexity Analysis

Time Complexity: O(n)

We visit each node once in the binary tree to find all paths with the target sum.

Space Complexity: O(n)

We use O(n) space to store the paths in the binary tree.

Breakdown:

    Algorithmic Patterns

    Depth First Search (DFS)

    How it's used: To traverse all paths in a tree and find the desired path sum

    Where in code: Tree traversal problems

    Example: Path Sum II, Path Sum III, Maximum Depth of Binary Tree

    Common Mistakes

    Mistake 1

    What: Forgetting to add the current node to the path during traversal.

    Why: This results in incorrect paths being considered for the sum.

    How to avoid: Ensure to add the current node to the path when exploring the tree.

    Mistake 2

    What: Not creating a deep copy of the current path to add to the result list.

    Why: Modifying the same path reference leads to incorrect results for different paths.

    How to avoid: Make a deep copy of the current path before adding it to the result list.

    Mistake 3

    What: Using the same list for tracking the current path and result paths.

    Why: This mixes up the current path and result paths, leading to incorrect results.

    How to avoid: Maintain separate lists for the current path and result paths during traversal.

    Interview Tips

    • Understand the problem requirements clearly before starting to code.
    • Use a recursive approach to traverse the tree and track the current path and sum.