LeetCode Hot 100 Guide#
LeetCode Hot 100 指路：https://leetcode.cn/studyplan/top-100-liked/
Actually, this is already the second round, and if you don't practice, you'll easily lose your touch =)
Hashing#
Arrays, HashSet, HashMap.
1. Two Sum#
To return the array index, you need to record both the number and its index, using HashMap.
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[0];
}
}
49. Group Anagrams#
Use a HashMap, where the key is the word sorted in order, and the value is a list containing all anagrams of that word.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map = new HashMap<>();
for(String str:strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List<String> list = map.getOrDefault(key, new ArrayList<>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
128. Longest Consecutive Sequence#
The key is to find the starting point of the consecutive sequence.
class Solution {
public int longestConsecutive(int[] nums) {
int max = 0;
int count = 0;
HashSet<Integer> set = new HashSet<>();
for(int num : nums) {
set.add(num);
}
for(int num : set) {
if(!set.contains(num-1)) { // start point
count = 0;
while(set.contains(num)) {
num++;
count++;
}
max = max < count ? count : max;
}
}
return max;
}
}
Two Pointers#
Two pointers mainly consist of two types: inward pointers and fast-slow pointers.
Reference: Two Pointers Technique to Solve Seven Array Problems
283. Move Zeroes#
class Solution {
public void moveZeroes(int[] nums) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
for(;slow<nums.length;slow++) { // fill 0
nums[slow] = 0;
}
}
}
11. Container With Most Water#
Reference: [Extended Discussion](https://labuladong.online/algo/frequency-interview/trapping-rain-water/#Extended Discussion)
Inward pointers approach, approaching from both sides to the middle, the shorter side moves towards the center, recording the maximum value during the process.
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int max = 0;
while (left < right) {
int v = Math.min(height[left], height[right]) * (right - left);
if (v > max) {
max = v;
}
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
15. 3Sum#
Reference: One Method to Eliminate nSum Problems
Exhaustion, first determine the first number, which turns it into a two-sum problem.
The array must be sorted to use the two-pointer technique.
The key to this problem is deduplication.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // Must sort first to ensure accurate traversal
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0)
break;
if (i >= 1 && nums[i - 1] == nums[i])
continue; // Deduplication for the first number nums[i]
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
List<Integer> ans = new ArrayList<>();
ans.add(nums[i]);
ans.add(nums[left]);
ans.add(nums[right]);
result.add(ans);
while (right > left && nums[right] == nums[right - 1])
right--; // Deduplication for nums[right]
while (right > left && nums[left] == nums[left + 1])
left++; // Deduplication for nums[left]
left++;
right--; // To find all possible combinations, cannot break
} else if (sum > 0)
right--;
else if (sum < 0)
left++;
}
}
return result;
}
}
42. Trapping Rain Water#
Reference: How to Efficiently Solve the Rainwater Trapping Problem
Local thinking, how much water can be held at a position is determined by the minimum height of the highest column on the left and the highest column on the right. The brute force algorithm is to traverse all positions' left and right columns, and the optimization point is to calculate once and record it, so that we don't have to calculate for each position again.
class Solution {
public int trap(int[] height) {
int[] lmax = new int[height.length]; // The height of the highest column on the left for each position
int[] rmax = new int[height.length]; // The height of the highest column on the right for each position
lmax[0] = height[0];
rmax[height.length-1] = height[height.length-1];
for(int i=1;i<height.length;i++) {
lmax[i] = Math.max(lmax[i-1], height[i]);
}
for(int i=height.length-2;i>=0;i--) {
rmax[i] = Math.max(rmax[i+1], height[i]);
}
int result = 0;
for(int i=0;i<height.length;i++) {
result = result + Math.min(lmax[i], rmax[i]) - height[i];
}
return result;
}
}
The two-pointer solution does not use a memo, calculating while traversing, saving space complexity. lmax is the maximum height from 0 to left, and rmax is the maximum height from right to the far right. If lmax is smaller, it counts as the left position, and vice versa.
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int lmax = 0, rmax = 0;
int result = 0;
while (left < right) {
lmax = Math.max(height[left], lmax);
rmax = Math.max(height[right], rmax);
if(lmax < rmax) {
result = result + lmax - height[left];
left++;
} else {
result = result + rmax - height[right];
right--;
}
}
return result;
}
}
Sliding Window#
Reference: I Wrote a Poem, Turning the Sliding Window Algorithm into a Dictation Question
The sliding window is essentially a technique for using fast and slow pointers. Pay attention to invariants, and it is recommended that the window interval be left-closed and right-open.
3. Longest Substring Without Repeating Characters#
Reference: [Four, Longest Substring Without Repeating Characters](https://labuladong.online/algo/essential-technique/sliding-window-framework/#Four, Longest Substring Without Repeating Characters)
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> window = new HashSet<>();
char[] chars = s.toCharArray();
int left = 0, right = 0; // Left-closed, right-open
int max = 0;
while(right < chars.length) {
char c = chars[right];
while(window.contains(c)) { // Shrink the window
window.remove(chars[left]);
left++;
}
window.add(c); // Expand the window
right++;
max = max >= (right - left) ? max : (right - left);
}
return max;
}
}
438. Find All Anagrams in a String#
Reference: [Three, Find All Anagrams](https://labuladong.online/algo/essential-technique/sliding-window-framework/#Three, Find All Anagrams)
This problem has two key points: one is the condition for shrinking, and the other is how to determine if it is an anagram.
The shrinking condition can be maintained by a fixed-length window, which is when the length equals the length of p, shrinking a bit, like a caterpillar crawling.
Determining an anagram is determined by two factors: the fixed-length window mentioned above and recording the number of elements with the same count. As long as the number of elements is the same, valid increases by 1. You don't have to worry about how to handle the case where the count of that letter exceeds the required count, because the fixed-length window limits that if this letter exceeds, other letters won't meet the requirement of valid + 1, so it won't be an anagram. The decrease of valid is achieved during the window shrink.
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character, Integer> need = new HashMap<>(); // <letter, occurrence count>
HashMap<Character, Integer> window = new HashMap<>();
for (char c : p.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
List<Integer> res = new ArrayList<>();
int left = 0, right = 0; // Left-closed, right-open
int valid = 0;
char[] chars = s.toCharArray();
while (right < chars.length) {
char c = chars[right];
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
right++;
while ((right - left) >= p.length()) {
if (valid == need.size()) { // Check if it is an anagram before shrinking
res.add(left);
}
char d = chars[left];
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) { // Check before removing
valid--;
}
window.put(d, window.get(d) - 1);
}
left++;
}
}
return res;
}
}
Note: In Java, when comparing the sizes of two Integer objects, using the == operator may lead to unexpected results because the == operator compares object references, not object values. To compare the values of two Integer objects, you should use the .equals() method or unbox them to the primitive type int.
Substring#
560. Subarray Sum Equals K#
Prefix sum technique.
Reference: Small and Beautiful Algorithm Technique: Prefix Sum Array day4_prefixSum2
class Solution {
public int subarraySum(int[] nums, int k) {
/**
* By calculating the prefix sum, the problem is transformed into solving the case where the difference between two prefix sums equals k.
* Suppose the prefix sum array is prefixSum, where prefixSum[i] represents the sum of elements from [0,i].
* For any two indices i and j (i<j), if prefixSum[j] - prefixSum[i] = k,
* then the sum of elements at positions [i+1,j] equals k.
* By traversing the array, calculating the prefix sum at each position, and using a hash table to store the occurrence count of each prefix sum.
* During the traversal, we check if there exists a prefix sum of prefixSum[j]-k (current cursor is j)
* If it exists, it means that the sum of the continuous subarray from a certain position to the current position equals k, and we accumulate the corresponding count into the result.
* Thus, by traversing the array once, we can count the number of continuous subarrays that sum to k, with a time complexity of O(n), where n is the length of the array.
*/
int count = 0;
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>(); // <prefix sum, occurrence count>
map.put(0, 1); // Used to solve the case where the sum from index 0 to index i equals k, convenient for unified processing
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k)) {
count += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
239. Sliding Window Maximum#
Monotonic queue.
Reference: Monotonic Queue Structure Solving Sliding Window Problems
Maintain a monotonically decreasing queue, where the front element is the maximum value in the window. Note that in the actual implementation, the queue should store indices to correctly remove elements from the left side when the window shifts to the right.
You can use a deque to simulate a monotonic queue, similar to a stack.
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Deque<Integer> queue = new ArrayDeque<>(); // Deque simulating monotonic queue
for (int i = 0; i < k; i++) {
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
}
res[0] = nums[queue.peekFirst()];
for (int i = k; i < nums.length; i++) {
if (i - k == queue.peekFirst()) {
queue.pollFirst();
}
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
res[i - k + 1] = nums[queue.peekFirst()];
}
return res;
}
}
76. Minimum Window Substring#
A typical sliding window problem, the idea is similar to 438. Find All Anagrams in a String.
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
for(char c:t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0)+1);
}
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int valid = 0;
int start = 0, len = s.length()+1; // Used to capture the result
while (right<s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0)+1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
while (valid >= need.size()) {
char d = s.charAt(left);
if(right-left < len) { // Save once first
start = left;
len = right - left;
}
if(need.containsKey(d)) {
if(window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d)-1);
}
left++;
}
}
if(len == s.length()+1) {
return "";
}
return s.substring(start, start+len);
}
}
Ordinary Arrays#
53. Maximum Subarray#
Reference: 4. Maximum Subarray
Greedy thinking, directly simulate, sum records whether the local sum is less than 0, if less than 0, discard it, res records the maximum value result.
class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
res = sum > res ? sum : res; // Take the maximum value of the interval accumulation (equivalent to constantly determining the maximum subarray termination position)
if (sum < 0) { // Equivalent to resetting the starting position of the maximum subarray, because encountering a negative number must lower the total
sum = 0;
}
}
return res;
}
}
Another greedy implementation, essentially the same.
class Solution {
public int maxSubArray(int[] nums) {
int preSum = 0;
int maxSum = Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++) {
if(preSum<=0) {
maxSum = Math.max(nums[i], maxSum);
preSum = nums[i];
} else {
maxSum = Math.max(nums[i] + preSum, maxSum);
preSum = nums[i]+preSum;
}
}
return maxSum;
}
}
Dynamic programming implementation:
class Solution {
public int maxSubArray(int[] nums) {
// dp[j] is the maximum sum of the continuous subarray ending with nums[j]
// dp[i] = Math.max(dp[i], dp[i-1]+nums[i])
int[] dp = new int[nums.length];
// Initial value dp[i] = nums[i]
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); // Either continue or start from scratch
res = Math.max(res, dp[i]);
}
return res;
}
}
The prefix sum idea is also very clever:
class Solution {
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE;
int minPreSum = 0;
int preSum = 0;
for (int x : nums) {
preSum += x; // Current prefix sum
ans = Math.max(ans, preSum - minPreSum); // Subtract the minimum prefix sum
minPreSum = Math.min(minPreSum, preSum); // Maintain the minimum prefix sum
}
return ans;
}
}
56. Merge Intervals#
Reference: 20. Merge Intervals
Determine interval overlap, sort first and then process. This can be considered a greedy strategy.
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> x[0] - y[0]); // Sort by left boundary
List<int[]> res = new ArrayList<>();
int start = intervals[0][0]; // Left boundary
int rightBound = intervals[0][1]; // Right boundary
for(int i = 1;i<intervals.length;i++) {
if(intervals[i][0]<=rightBound) { // Interval overlap
rightBound = Math.max(intervals[i][1], rightBound);
} else {
res.add(new int[]{start, rightBound}); // Non-overlapping interval
start = intervals[i][0];
rightBound = intervals[i][1];
}
}
res.add(new int[]{start, rightBound});
return res.toArray(new int[res.size()][]);
}
}
189. Rotate Array#
A pure technique question, the simplest way is to use an extra array to place the original array element at index i into the new array at index (i+k)modn.
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] newArr = new int[n];
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i];
}
System.arraycopy(newArr, 0, nums, 0, n);
}
}
If you find the pattern, you can use the three-time array reversal to achieve it:
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
}
}
238. Product of Array Except Self#
First calculate the prefix product array and the suffix product array, then traverse once to calculate the result, prefix product x suffix product.
Actually, the process of calculating the prefix and suffix arrays can also be seen as a very simple dynamic programming.
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] answer = new int[nums.length];
int[] prefix = new int[nums.length];
int[] suffix = new int[nums.length];
prefix[0] = 1;
suffix[nums.length - 1] = 1;
for (int i = 1; i < nums.length; i++) {
prefix[i] = prefix[i - 1] * nums[i - 1];
}
for (int i = nums.length - 2; i >= 0; i--) {
suffix[i] = suffix[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
answer[i] = prefix[i] * suffix[i];
}
return answer;
}
}
41. First Missing Positive#
Reference: First Missing Positive
First, note the pigeonhole principle. For an array of length N, the smallest positive integer that does not appear must be in the range [1, N+1].
If there are no additional time-space complexity requirements, it is easy to think of putting all numbers into a hash table, and then enumerating positive integers starting from 1 to check if they are in the hash table, with a time complexity of O(N), and space complexity of O(N).
To reduce space complexity, we must use the given array to store some states, transforming the given array into a hash table.
Traverse the array, and for the number x that is in the range [1,N], mark the position of the x−1 index (note: array index starts from 0). After the traversal, if all positions are marked, the answer is N+1; otherwise, the answer is the smallest unmarked position plus 1.
class Solution {
public int firstMissingPositive(int[] nums) {
// First exclude non-positive integers
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= 0) {
nums[i] = Integer.MAX_VALUE;
}
}
// Traverse the array, mark the numbers in the range [1, n]
// Set nums[x-1] to negative
for (int i = 0; i < nums.length; i++) {
int num = Math.abs(nums[i]); // Take the absolute value to avoid skipping unvisited but marked negative numbers
if (num >= 1 && num <= nums.length) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
// Last traversal, check the marks
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) { // Not marked
return i + 1;
}
}
return nums.length + 1;
}
}
Besides marking, you can also achieve it through swapping, making the x−1 element equal to x. Each mismatched position represents a missing positive number.
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // Note to avoid infinite loops
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
Matrix#
73. Set Matrix Zeroes#
A solution with space complexity O(m+n) uses two hash tables to store the row and column indices of the zero values, and then traverses to set them to zero.
class Solution {
public void setZeroes(int[][] matrix) {
HashSet<Integer> rows = new HashSet<>();
HashSet<Integer> columns = new HashSet<>();
for(int i=0;i<matrix.length;i++) {
for(int j=0;j<matrix[0].length;j++) {
if(matrix[i][j]==0) {
rows.add(i);
columns.add(j);
}
}
}
for(int i : rows) {
for(int j=0;j<matrix[0].length;j++) {
matrix[i][j] = 0;
}
}
for(int j:columns) {
for(int i=0;i<matrix.length;i++) {
matrix[i][j] = 0;
}
}
}
}
54. Spiral Matrix#
Reference: Fancy Traversal Techniques for Two-Dimensional Arrays
The core idea of the solution is to traverse the array in the order of right, down, left, and up, using four variables to define the boundaries of the untraversed elements.
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int upper_bound = 0, lower_bound = m - 1;
int left_bound = 0, right_bound = n - 1;
List<Integer> res = new ArrayList<>();
while (res.size() < m * n) { // Traversal complete when equal
// Traverse from left to right at the top, note that the interval is left-closed and right-closed
if (upper_bound <= lower_bound) { // Only traverse this row if this condition is met
for (int i = left_bound; i <= right_bound; i++) {
res.add(matrix[upper_bound][i]);
}
upper_bound++;
}
// Traverse down the right side
if (left_bound <= right_bound) {
for (int i = upper_bound; i <= lower_bound; i++) {
res.add(matrix[i][right_bound]);
}
right_bound--;
}
// Traverse from right to left at the bottom
if (upper_bound <= lower_bound) {
for (int i = right_bound; i >= left_bound; i--) {
res.add(matrix[lower_bound][i]);
}
lower_bound--;
}
// Traverse from bottom to top on the left side
if (left_bound <= right_bound) {
for (int i = lower_bound; i >= upper_bound; i--) {
res.add(matrix[i][left_bound]);
}
left_bound++;
}
}
return res;
}
}
48. Rotate Image#
Pure technique, use flipping instead of rotating, first flip the matrix along the diagonal, then flip each row of the matrix.
class Solution {
public void rotate(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < i; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - j - 1];
matrix[i][matrix.length - j - 1] = tmp;
}
}
}
}
240. Search a 2D Matrix II#
Observe the matrix in the example. If you start searching from the top left corner, if the target value is greater than the number in the top left corner, then the subsequent search direction has two options: left or down. The same applies if you start from the bottom right corner. However, starting from the other two corners is completely different.
Linear search, the official solution is called Z-shaped search:
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
i--;
} else {
j++;
}
}
return false;
}
}
You can also use binary search on each row.
Linked List#
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
160. Intersection of Two Linked Lists#
Reference: [Whether Two Linked Lists Intersect](https://labuladong.online/algo/essential-technique/linked-list-skills-summary-2/#Whether Two Linked Lists Intersect)
The key to solving this problem is to find a way for p1 and p2 to reach the intersection node simultaneously.
You can do this by pre-calculating the lengths of the two linked lists to align the tails:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// First, find the lengths of the two linked lists
int lenA = 0, lenB = 0;
ListNode node = headA;
while(node!=null) {
lenA++;
node=node.next;
}
node = headB;
while(node!=null) {
lenB++;
node = node.next;
}
// Let ListA be the shorter linked list
if(lenA>lenB) {
node = headA;
headA = headB;
headB = node;
int tmp = lenA;
lenA = lenB;
lenB = tmp;
}
// Fast-slow pointer start, fast pointer moves first
for(int i=0;i<lenB-lenA;i++) {
headB = headB.next;
}
while(headA!=null && headB!=null) {
if(headA==headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}
A more clever way is to concatenate the two linked lists, allowing p1 to traverse list A and then start traversing list B, and p2 to traverse list B and then start traversing list A. This way, they will logically connect the two linked lists together.
(Version 2) Merging Linked Lists to Achieve Synchronized Movement
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1 points to the head node of list A, p2 points to the head node of list B
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1 moves one step, if it reaches the end of list A, it moves to list B
if (p1 == null) p1 = headB;
else p1 = p1.next;
// p2 moves one step, if it reaches the end of list B, it moves to list A
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
}
206. Reverse Linked List#
Two-pointer method:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while (cur!=null) {
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
Head-insertion method, higher space complexity:
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null)
return null;
ListNode resultList = new ListNode(head.val, null);
ListNode currentNode = head;
while(currentNode.next != null) {
currentNode = currentNode.next;
ListNode toAdd = new ListNode(currentNode.val, resultList);
resultList = toAdd;
}
return resultList;
}
}
Recursive method, reference: Recursive Magic: Reverse a Singly Linked List
class Solution {
// Definition: Input a singly linked list head node, reverse the linked list, and return the new head node
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) { // Base case for recursion
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
}
234. Palindrome Linked List#
Reference: How to Determine a Palindrome Linked List Palindrome Linked List
Method 1: Copy values into an array and use two-pointer method. No technical content.
Method 2: Fast-slow pointer. Reverse the second half of the linked list (modify the linked list structure), then compare the first half and the second half. After comparison, we should restore the linked list.
Method 3: Use recursion to simulate two-pointer implementation of palindrome checking.
class Solution {
ListNode left; // Pointer moving from left to right
public boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right) {
if (right == null) {
return true;
}
if (traverse(right.next)) {
if (left.val == right.val) {
left = left.next;
return true;
}
}
return false;
}
}
141. Linked List Cycle#
Reference: [Determine Whether a Linked List Contains a Cycle](https://labuladong.online/algo/essential-technique/linked-list-skills-summary-2/#Determine Whether a Linked List Contains a Cycle)
Fast-slow pointer technique, the slow pointer moves one step, the fast pointer moves two steps. If the fast and slow pointers meet, it indicates that there is a cycle.
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
Actually, I don't quite understand the judgment condition for the fast pointer moving two steps. When to use (fast != null && fast.next != null) and when to use (fast.next != null && fast.next.next != null)?
142. Linked List Cycle II#
Reference: [Determine Whether a Linked List Contains a Cycle](https://labuladong.online/algo/essential-technique/linked-list-skills-summary-2/#Determine Whether a Linked List Contains a Cycle) 8. Linked List Cycle II
It’s also a fast-slow pointer, but this time we need to return the entry point of the cycle. Just return the slow pointer to the head, and then let slow and fast start at the same pace again. The position where they meet again is the entrance to the cycle.
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
21. Merge Two Sorted Lists#
Reference: [Merge Two Sorted Lists](https://labuladong.online/algo/essential-technique/linked-list-skills-summary-2/#Merge Two Sorted Lists)
This problem is very simple, iteratively perform tail insertion, and note that using a dummy head node will be more convenient, so be good at using it.
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode p = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
p.next = list1;
list1 = list1.next;
} else {
p.next = list2;
list2 = list2.next;
}
p = p.next; // p keeps moving forward
}
if (list1 == null) {
p.next = list2;
}
if (list2 == null) {
p.next = list1;
}
return dummy.next;
}
}
2. Add Two Numbers#
This problem feels similar to merging sorted lists, nothing much to say, just pay attention to adding an extra node when there is still a carry.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode p = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int val1 = l1 == null ? 0 : l1.val;
int val2 = l2 == null ? 0 : l2.val;
int sum = val1 + val2 + carry;
ListNode node = new ListNode(sum % 10);
carry = sum / 10;
p.next = node;
p = p.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry != 0) {
p.next = new ListNode(carry);
}
return dummy.next;
}
}
19. Remove Nth Node From End of List#
Reference: [The Nth Node from the End of a Singly Linked List](https://labuladong.online/algo/essential-technique/linked-list-skills-summary-2/#The Nth Node from the End of a Singly Linked List)
At a glance, the fast-slow pointer, and the fast-slow pointer solution ideas for the intersecting linked list and the palindrome linked list are consistent.
The basic approach is for the fast pointer to move a few steps first, then the fast and slow pointers move together, so the distance between the two pointers is fixed, making it easy to find a specific position.
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode slow = dummy, fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
Note that the technique of using a dummy head node is to prevent null pointer exceptions.
24. Swap Nodes in Pairs#
Reference: 5. Swap Nodes in Pairs
The idea of this problem is similar to reversing a linked list, which is a two-pointer method. Also, be sure to get used to using a dummy head node.
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(-1, head);
ListNode cur = dummyHead;
// Only swap if there are two nodes
while (cur.next != null && cur.next.next != null) {
ListNode tmp = cur.next;
cur.next = cur.next.next;
ListNode tmp1 = cur.next.next;
cur.next.next = tmp;
tmp.next = tmp1;
cur = cur.next.next;
}
return dummyHead.next;
}
}
You can also implement it recursively, which is easy to understand:
class Solution {
public ListNode swapPairs(ListNode head) {
// Base case: insufficient two nodes
if (head == null || head.next == null) {
return head;
}
ListNode next1 = head.next;
ListNode next2 = swapPairs(head.next.next); // Recursion
head.next = next2;
next1.next = head;
return next1;
}
}
25. Reverse Nodes in k-Group#
Reference: How to Reverse a Linked List in k-Group
This problem should be linked to 206. Reverse Linked List, using iteration to implement the function of reversing a part of the linked list, and finally concatenating the linked lists together. Using recursion to solve this problem is much more elegant than iteration (and iteration is just a while loop).
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) {
return null;
}
ListNode a = head, b = head;
for (int i = 0; i < k; i++) {
if (b == null) {
return head; // Base case: total number of nodes < k
}
b = b.next;
}
ListNode newHead = reverse(a, b);
a.next = reverseKGroup(b, k); // a is the tail node after the interval [a, b] is reversed
return newHead;
}
// Reverse elements in the interval [a, b), note that it is left-closed and right-open
ListNode reverse(ListNode a, ListNode b) {
ListNode pre = null, cur = a, nxt = a;
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
138. Copy List with Random Pointer#
Reference: Copy a Linked List with Random Pointer
The first solution is backtracking + hash table, using a hash table to record the creation status of each node. During the traversal of the linked list, check the creation status of the "successor node of the current node" and the "node pointed to by the random pointer of the current node". If any of these two nodes has not been created, we immediately create it recursively. When the copy is complete and we backtrack to the current layer, we can complete the pointer assignment for the current node. Note that a node may be pointed to by multiple other nodes, so it may recursively attempt to copy a certain node multiple times. To prevent duplicate copies, we need to check whether the current node has been copied first. If it has been copied, we can directly retrieve the pointer to the copied node from the hash table and return it.
class Solution {
HashMap<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if (map.containsKey(head)) {
return map.get(head);
}
Node newHead = new Node(head.val);
map.put(head, newHead);
newHead.next = copyRandomList(head.next);
newHead.random = copyRandomList(head.random);
return newHead;
}
}
Actually, the above lengthy explanation is overly complicated. You can directly traverse the linked list once, put the nodes and their corresponding new nodes into the hash table, and then traverse the linked list again to assign the next and random pointers of each new node, directly retrieving the nodes from the hash table.
class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
Node cur = head;
HashMap<Node,Node> map = new HashMap<>();
while(cur!=null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur=head;
while(cur!=null){
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
}
There is also a solution using iteration + node splitting, which I call the interleaved insertion method. It requires three traversals in total: the first traversal creates new nodes and inserts them into the original nodes; the second traversal copies the random pointers; the third traversal separates the new linked list from the original linked list.
148. Sort List#
Insertion sort (147. Insertion Sort List):
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(-1, head); // Convenient for inserting nodes before head
ListNode last = head; // Maintain the last node of the sorted part
ListNode cur = head.next; // Node to be inserted
while (cur != null) {
if (cur.val >= last.val) {
last = cur;
} else {
ListNode ptr = dummy;
while (ptr != last) {
if (cur.val <= ptr.next.val) {
last.next = cur.next;
cur.next = ptr.next;
ptr.next = cur;
break;
} else {
ptr = ptr.next;
}
}
}
cur = last.next;
}
return dummy.next;
}
}
Top-down merge sort:
The first step is to find the midpoint to split the linked list using the fast-slow pointer technique; the second step is to sort the two sub-linked lists recursively; the third step is to merge the sorted linked lists using the method of 21. Merge Two Sorted Lists.
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) { // Base case
return head;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rightHead = slow.next;
slow.next = null; // Find the midpoint and split the linked list
ListNode left = sortList(head);
ListNode right = sortList(rightHead); // Recursively sort
return merge(left, right);
}
ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (a != null && b != null) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
if (a == null) {
cur.next = b;
} else {
cur.next = a;
}
return dummy.next;
}
}
The space complexity of top-down merge sort is O(logn), while using the bottom-up merge sort method can achieve O(1) space complexity. But actually, there is not much necessity.
23. Merge K Sorted Lists#
Reference: [Merge k Sorted Lists](https://labuladong.online/algo/essential-technique/linked-list-skills-summary-2/#Merge k Sorted Lists)
Similar to 21. Merge Two Sorted Lists, the key is how to quickly find the smallest value among K nodes, which can be optimized using a priority queue.
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists) { // Add the head nodes of k linked lists to the min heap
if (head != null) {
pq.add(head);
}
}
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
p.next = node;
p = node;
if (node.next != null) {
pq.add(node.next);
}
}
return dummy.next;
}
}
146. LRU Cache#
Reference: Algorithms Are Like Building Lego: Hand-rolling the LRU Algorithm
Hash table mapping + doubly linked list = Hash linked list LinkedHashMap
class LRUCache {
HashMap<Integer, Node> map = new HashMap<>();
DoubleLinkedList linkedlist = new DoubleLinkedList();
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node node = map.get(key);
linkedlist.remove(node); // Move the accessed node to the end of the list
linkedlist.addLast(node);
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
linkedlist.remove(node); // Move the updated node to the end of the list
node.value = value; // Update value
linkedlist.addLast(node);
} else {
Node node = new Node(key, value);
map.put(key, node);
linkedlist.addLast(node);
if (linkedlist.size() > capacity) {
Node removed = linkedlist.removeFirst();
map.remove(removed.key);
}
}
}
}
class Node {
int key, value;
Node next, prev;
public Node() {}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
class DoubleLinkedList {
Node head, tail; // Dummy head and tail nodes
int size;
public DoubleLinkedList() {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
this.size = 0;
}
public Node addLast(Node node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
size++;
return node;
}
public Node removeFirst() {
if (size == 0) {
return null;
}
Node node = head.next;
remove(node);
return node;
}
public void remove(Node node) {
node.next.prev = node.prev;
node.prev.next = node.next;
size--;
}
public int size() {
return this.size;
}
}
You can also use Java's built-in type LinkedHashMap to implement the LRU algorithm.
Binary Tree#
Reference: Dong Ge Leads You to Brush Binary Trees (Outline) 1. Basic Theory of Binary Trees
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
94. Binary Tree Inorder Traversal#
Recursive inorder traversal:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traverse(root, res);
return res;
}
void traverse(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
traverse(root.left, res);
res.add(root.val);
traverse(root.right, res);
}
}
104. Maximum Depth of Binary Tree#
The recursive idea is to decompose the problem. The maximum depth of a binary tree is the maximum depth of its left and right subtrees plus one.
The maximum depth is usually defined as the longest path from a node to a leaf node, while depth usually refers to the path length from the root node to a certain node. (Sometimes it is the number of nodes rather than the path length.)
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
226. Invert Binary Tree#
Post-order traversal, recursively invert the left and right subtrees.
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.right = left;
root.left = right;
return root;
}
}
101. Symmetric Tree#
Two trees are mirrors of each other if they satisfy the following conditions: 1. The values of the root nodes are equal; 2. The left subtree of each tree is a mirror of the right subtree of the other tree.
The previous approach is to recursively compare the "left subtree's left subtree" with the "right subtree's right subtree," and the "left subtree's right subtree" with the "right subtree's left subtree."
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return false;
return compare(root.left,root.right);
}
boolean compare(TreeNode left, TreeNode right) {
if(left==null && right!=null) return false;
else if(left!=null && right==null) return false;
else if(left==null && right ==null) return true;
else if(left!=null && right!=null && left.val!=right.val) return false;
else {
if(compare(left.left,right.right)&&compare(left.right,right.left))
return true;
else return false;
}
}
}
More elegantly, synchronize two pointers to traverse, which is essentially the same.
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) { // Only one is null
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}
543. Diameter of Binary Tree#
For each node of the tree, the maximum diameter is the sum of the "height of the left subtree" and the "height of the right subtree," using post-order recursive traversal.
Height usually refers to the longest path from a node to a leaf node, while depth usually refers to the path length from the root node to a certain node. (Sometimes it is the number of nodes rather than the path length.)
class Solution {
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxHeight(root);
return maxDiameter;
}
int maxHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = maxHeight(root.left);
int rightHeight = maxHeight(root.right);
// Update the maximum diameter
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
// Return the maximum height of the current node
return Math.max(leftHeight, rightHeight) + 1;
}
}
102. Binary Tree Level Order Traversal#
Level order traversal is essentially breadth-first traversal in graph theory, which requires the use of an auxiliary data structure, a queue.
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
// while loop, traversing each level of the tree from top to bottom
while (!queue.isEmpty()) {
List<Integer> list = new ArrayList<>();
int size = queue.size();
// for loop, traversing each node in this level from left to right
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
list.add(node.val);
}
res.add(list);
}
return res;
}
}
108. Convert Sorted Array to Binary Search Tree#
Reference: 32. Convert Sorted Array to Binary Search Tree
Constructing a binary tree from an array essentially involves finding the partition point, which serves as the current node, and then recursively processing the left and right intervals based on the size of the left and right subarrays.
Constructing a binary tree uses pre-order traversal.
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return traverse(nums, 0, nums.length);
}
// [begin, end) left-closed, right-open
TreeNode traverse(int[] nums, int begin, int end) {
if (begin >= end) {
return null;
}
int mid = begin + (end - begin) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = traverse(nums, begin, mid);
root.right = traverse(nums, mid + 1, end);
return root;
}
}
98. Validate Binary Search Tree#
Reference: 23. Validate Binary Search Tree
A more intuitive method is to perform an in-order traversal and place the values into an array to check if the array is sorted. You can also directly check if it is sorted during the in-order traversal.
This problem is easy to make mistakes, and the easy mistake point is that you cannot simply compare the left node being less than the middle node and the right node being greater than the middle node. Instead, you need to compare all nodes in the left subtree being less than the middle node and all nodes in the right subtree being greater than the middle node. This requires using a global variable to store the current maximum value to compare whether the traversed node is sorted.
class Solution {
TreeNode max;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (max != null && max.val >= root.val) {
return false;
}
max = root;
return isValidBST(root.right);
}
}
230. Kth Smallest Element in a BST#
In-order traversal, counting:
class Solution {
int count = 0;
int result = -1;
public int kthSmallest(TreeNode root, int k) {
inorderTravel(root, k);
return result;
}
void inorderTravel(TreeNode root, int k) {
if (root == null)
return;
inorderTravel(root.left, k);
count++;
if (count == k) {
result = root.val;
return;
}
inorderTravel(root.right, k);
}
}
If you need to frequently find the k-th smallest value, you can record the number of nodes in each subtree:
class Solution {
// Store the number of nodes in the subtree rooted at each node
HashMap<TreeNode, Integer> map = new HashMap<>();
public int kthSmallest(TreeNode root, int k) {
count(root);
while (root != null) {
int left = map.getOrDefault(root.left, 0);
if (left > k - 1) {
root = root.left;
} else if (left < k - 1) {
root = root.right;
k = k - (left + 1);
} else {
break;
}
}
return root.val;
}
// Post-order recursive traversal to count the number of nodes in the subtree rooted at root
int count(TreeNode root) {
if (root == null) {
return 0;
}
int left = count(root.left);
int right = count(root.right);
map.put(root, left + right + 1);
return left + right + 1;
}
}
199. Binary Tree Right Side View#
Level order traversal, only taking the rightmost element of each level:
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (i == size - 1) {
res.add(node.val);
}
}
}
return res;
}
}
114. Flatten Binary Tree to Linked List#
Reference: Detailed and Simple Idea Analysis, Multiple Solutions
The modified post-order traversal (first visit the right subtree) uses a global variable pre to record the last traversed node, connecting the linked list from the end.
class Solution {
TreeNode pre = null; // The pointer to the last traversed node
public void flatten(TreeNode root) {
if (root == null) {
return;
}
flatten(root.right);
flatten(root.left);
root.right = pre;
root.left = null;
pre = root;
return;
}
}
105. Construct Binary Tree from Preorder and Inorder Traversal#
Reference: 18. Construct Binary Tree from Inorder and Postorder Traversal
The first element of the preorder traversal sequence is the root node, which is the partition point. Based on this element's position in the inorder traversal sequence, we can split it into the inorder traversal sequence (left) and the inorder traversal sequence (right). Then, based on the size of the left and right subarrays, we can also split the preorder traversal sequence into left and right subarrays, allowing us to recursively process them happily.
Constructing a binary tree uses pre-order traversal.
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return construct(preorder, 0, preorder.length,
inorder, 0, inorder.length);
}
// [begin, end) left-closed, right-open
TreeNode construct(int[] preorder, int begin_pre, int end_pre,
int[] inorder, int begin_in, int end_in) {
if (begin_pre >= end_pre) {
return null;
}
int mid = begin_pre + (end_pre - begin_pre) / 2;
TreeNode root = new TreeNode(preorder[mid]);
root.left = construct(preorder, begin_pre + 1, begin_pre + 1 + end_in - begin_in,
inorder, begin_in, mid);
root.right = construct(preorder, begin_pre + 1 + end_in - begin_in, end_pre,
inorder, mid + 1, end_in);
return root;
}
}
437. Path Sum III#
Reference: 17. Path Sum Path Sum III
Depth-first search recursively traverses all possible paths:
class Solution {
public int pathSum(TreeNode root, long targetSum) {
if (root == null) {
return 0;
}
int count = rootSum(root, targetSum);
count += pathSum(root.left, targetSum);
count += pathSum(root.right, targetSum);
return count;
}
// The number of paths starting from the root node
int rootSum(TreeNode root, long targetSum) {
if (root == null) {
return 0;
}
int count = 0;
if (root.val == targetSum) {
count++;
}
count += rootSum(root.left, targetSum - root.val);
count += rootSum(root.right, targetSum - root.val);
return count;
}
}
The depth-first search solution has a maximum time complexity of O(N*2) because for each node, it calculates the number of paths starting from that node, leading to many repeated calculations.
The prefix sum idea, similar to [560. Subarray Sum Equals K](https://