Learn DSA
Depth-First Search
Greedy Algorithms
Depth-First Search
Path Sum II
medium
DESCRIPTION (credit 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:
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
- The remaining target sum
- The values along the current path (starting from the root).
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[:])returndfs(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()
Solution
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
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)
.
Login to track your progress
Your account is free and you can post anonymously if you choose.