Search
⌘K
Get Premium
Depth-First Search
Path Sum II
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given the root of a binary tree and an integer target, write a recursive function to find all root-to-leaf paths where the sum of all the values along the path sum to target.
Example 1:
Input:
[1,2,4,4,7,5,1] target = 10
Output:
[[1,2,7],[1,4,5]] # [[1,4,5],[1,2,7]] is also accepted.
The paths are 1 -> 2 -> 7 and 1 -> 4 -> 5
Explanation
This problem is an extension of the Path Sum problem. In this problem, we are asked to return a list of all root-to-leaf paths where the sum of the nodes in the path equals a given target sum.
This is an example of a question which benefits from using a global variable that all recursive calls have access to store the list of all root-to-leaf paths that match the target sum.
Return Values
In this case question, we don't need our recursive calls to return any values. Instead, we use depth-first search to traverse each root-to-leaf path in the tree, while maintaining the state of the current path via parameters to the recursive call.
Base Case
We can stop recursing when our tree is empty.
Extra Work
At each node, we need to add the value of the node to the current path.
Whenever we are at a leaf node, we can check if the value of the current node matches the target. If it does, we can add the current path to the global list of paths.
Helper Function
Parent nodes need to pass two pieces of information down to their children:
- The remaining target sum
- The values along the current path (starting from the root).
These values must be passed down as parameters of the recursive call, so we need to introduce a helper function to help us recurse.
Global Variables
We will use a global variable to store the root-to-leaf paths that match the given target. This allows us to avoid having to return path arrays up the recursion stack and simplifies collecting all valid paths.
Solution
Python
def dfs(node, target, path):# base caseif not node:return# append current value to the pathpath.append(node.val)if not node.left and not node.right:if node.val == target:result.append(path[:])dfs(node.left, target - node.val, path)dfs(node.right, target - node.val, path)# when our code reaches here, are done exploring all# the root-to-leaf paths that go through the current node.# pop the current value from the path to prepare for the next pathpath.pop()
Global Variables
We can use a single global variable that all recursive calls have access to store the list of paths that add up to the target sum.
Solution
Solution
Python
class Solution:def pathSum(self, root, target):def dfs(node, target, path):# base caseif not node:return# append current value to the pathpath.append(node.val)if not node.left and not node.right:if node.val == target:result.append(path[:])dfs(node.left, target - node.val, path)dfs(node.right, target - node.val, path)# when our code reaches here, are done exploring all# the root-to-leaf paths that go through the current node.# pop the current value from the path to prepare for the next pathpath.pop()result = []dfs(root, target, [])return result
Animated Solution
Try these examples:
Visualization
Python
def pathSum(root, target):def dfs(node, target, path):if not node:returnpath.append(node.val)if not node.left and not node.right:if node.val == target:result.append(path[:])dfs(node.left, target - node.val, path)dfs(node.right, target - node.val, path)path.pop()result = []dfs(root, target, [])return result
path sum II
0 / 41
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(N) where N is the number of nodes in the binary tree. We visit each node via each recursive call to dfs exactly once. Each recursive call does a constant amount of work.
Space Complexity: O(N) where N is the number of nodes in the binary tree, for the space that it takes to allocate each recursive call frame on the call stack. The space taken up by the result list is in the worst case equal to the number of leaf nodes in the binary tree, which is also O(N).
Mark as read
Your account is free and you can post anonymously if you choose.