Path Sum II
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 returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2], [5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: []
Example 3:
Input: root = [1,2], targetSum = 0
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]
. -1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
Solution
We wish to fill in the template logic:
is_leaf
: whennode
is a leaf in the tree, and there is no remaining left.get_edges
: the children of the currentnode
(node.left
andnode.right
).is_valid
: an edge (node) is only invalid when it is non-empty (None
,null
).
In the implementation, we want to check whether node is None
first, so that we do not try to get the field of an empty object.
On the current node
, we calculate the remaining value after adding the current value.
Then we check whether the node
is a leaf so that path
is a root-to-leaf path and whether the remaining
value left is 0.
If these condition is satisfied, then we have found one solution. If not, we'd have to traverse further until we reach a leaf in the tree (may or may not be a solution).
The below implementation may look different than the template, but essentially one can update and revert path
and remaining
inside the if-else conditions to gain similarity to the template.
We had also left the check of node is None
on the outside to accommodate the use of node.val
(and to prevent the root
being empty).
Implementation
1def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
2 def dfs(node, remaining, path):
3 if (node is None): return
4 path.append(node.val) # update path
5 remaining -= node.val
6 if node.left is None and node.right is None and remaining == 0: # is_leaf
7 paths.append(path[:])
8 else: # edges = [node.left, node.right]
9 dfs(node.left, remaining, path)
10 dfs(node.right, remaining, path)
11 path.pop() # revert path
12
13 paths = []
14 dfs(root, targetSum, [])
15 return paths
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
What is the running time of the following code?
1int sqrt(int n) { 2 for (int guess = 1; guess * guess <= n; guess++) { 3 if (guess * guess == n) { 4 return guess; 5 } 6 } 7 return -1; 8}
Solution Implementation
Which data structure is used to implement priority queue?
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.