1.哈希
1.1 两数之和
代码实现（C++/Java）
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> map; for(int i=0;i<nums.size();i++){ if(map.count(target-nums[i])!=0){ return {i,map[target-nums[i]]}; } else { map[nums[i]]=i; } } return {}; } };
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map=new HashMap<>(); for(int i=0;i<nums.length;i++){ if(map.containsKey(target-nums[i])){ return new int[]{i,map.get(target-nums[i])}; }else { map.put(nums[i],i); } } return new int[]{}; } }
1.2 字母异位词分组
代码实现（C++/Java）
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; unordered_map<string,vector<string>> map; for(int i=0;i<strs.size();i++){ string t=strs[i]; sort(t.begin(),t.end()); map[t].push_back(strs[i]); } for(auto t:map){ res.push_back(t.second); } return res; } };
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String,List<String>> map=new HashMap<>(); for(String s:strs){ char[] ch=s.toCharArray(); Arrays.sort(ch); String key=new String(ch); map.computeIfAbsent(key,k->new ArrayList<>()).add(s); } return new ArrayList<>(map.values()); } }
1.3 最长连续序列
代码实现（C++/Java）
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> set; for(int i=0;i<nums.size();i++) set.insert(nums[i]); int res=0; for(int s:set){ if(!set.contains(s-1)){ int cur=s; int len=1; while(set.contains(cur+1)){ cur++; len++; } res=max(res,len); } } return res; } };
class Solution { public int longestConsecutive(int[] nums) { //HashSet(O(n)),TreeSet(nlogn) HashSet<Integer> set=new HashSet<>(); for(int i=0;i<nums.length;i++) set.add(nums[i]); int res=0; for(int t:set){ if(!set.contains(t-1)){ int cur=t; int len=1; while(set.contains(cur+1)){ cur++; len++; } res=Math.max(res,len); } } return res; } }
2.双指针
2.1 移动0
代码实现（C++/Java）
class Solution { public: void moveZeroes(vector<int>& nums) { int n=nums.size(); int j=0; for(int i=0;i<n;i++){ if(nums[i]!=0) nums[j++]=nums[i]; } for(int i=j;i<n;i++) nums[i]=0; } };
class Solution { public void moveZeroes(int[] nums) { int n=nums.length; int j=0; for(int i=0;i<n;i++){ if(nums[i]!=0){ nums[j++]=nums[i]; } } for(int i=j;i<n;i++){ nums[i]=0; } } }
2.2 盛水最多的容器
代码实现（C++/Java）
class Solution { public: int maxArea(vector<int>& height) { int n=height.size(); int l=0,r=n-1; int res=-1; while(r>l){ int a=r-l; int b=min(height[l],height[r]); res=max(res,a*b); if(height[l]<height[r]){ l++; }else { r--; } } return res; } };
class Solution { public int maxArea(int[] height) { int n=height.length; int l=0,r=n-1; int res=-1; while(r>l){ int a=r-l; int b=Math.min(height[l],height[r]); res=Math.max(res,a*b); if(height[l]<height[r]){ l++; } else { r--; } } return res; } }
2.3 三数之和
代码实现（C++/Java）
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; sort(nums.begin(),nums.end()); for(int i=0;i<nums.size();i++){ if(i>0 && nums[i]==nums[i-1]) continue; int l=i+1,r=nums.size()-1; while(r>l){ int sum=nums[i]+nums[l]+nums[r]; if(sum>0){ r--; } else if(sum<0){ l++; } else { vector<int> t; t.push_back(nums[i]); t.push_back(nums[l]); t.push_back(nums[r]); res.push_back(t); while(r>l && nums[r]==nums[r-1]) r--; while(r>l && nums[l]==nums[l+1]) l++; r--; l++; } } } return res; } };
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res=new ArrayList<>(); Arrays.sort(nums); for(int i=0;i<nums.length;i++){ if(i>0 && nums[i]==nums[i-1]) continue; int l=i+1,r=nums.length-1; while(r>l){ int sum=nums[i]+nums[l]+nums[r]; if(sum>0){ r--; } else if(sum<0){ l++; } else { List<Integer> t=new ArrayList<>(); t.add(nums[i]); t.add(nums[l]); t.add(nums[r]); res.add(t); while(r>l && nums[r]==nums[r-1]) r--; while(r>l && nums[l]==nums[l+1]) l++; r--; l++; } } } return res; } }
2.4 接雨水
代码实现（C++/Java）
class Solution { public: int trap(vector<int>& height) { int n=height.size(); int l=0,r=n-1; int lMax=0,rMax=0; int res=0; while(r>l){ if(height[l]<height[r]){ if(height[l]>lMax){ lMax=height[l]; }else { res+=lMax-height[l]; } l++; }else{ if(height[r]>rMax){ rMax=height[r]; } else { res+=rMax-height[r]; } r--; } } return res; } };
class Solution { public int trap(int[] height) { int n=height.length; int l=0,r=n-1; int lMax=0,rMax=0; int res=0; while(r>l){ if(height[l]<height[r]){ if(height[l]>lMax){ lMax=height[l]; }else { res+=lMax-height[l]; } l++; } else { if(height[r]>rMax){ rMax=height[r]; }else { res+=rMax-height[r]; } r--; } } return res; } }
3.滑动窗口
3.1 无重复字符的最长子串
代码实现（C++/Java）
class Solution { public: int lengthOfLongestSubstring(string s) { int n=s.size(); int last[128]; memset(last,-1,sizeof(last)); int l=0; int res=0; for(int i=0;i<n;i++){ char c=s[i]; if(last[c]>=l) l=last[c]+1; last[c]=i; res=max(res,i-l+1); } return res; } };
class Solution { public int lengthOfLongestSubstring(String s) { int n=s.length(); int[] last=new int[128]; Arrays.fill(last,-1); int res=0; int l=0; for(int i=0;i<n;i++){ char c=s.charAt(i); if(last[c]>=l) l=last[c]+1; last[c]=i; res=Math.max(res,i-l+1); } return res; } }
3.2 找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
代码实现（C++/Java）
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> res; int n=s.size(); int m=p.size(); int ss[26]; int pp[26]; for(int i=0;i<m;i++) pp[p[i]-'a']++; for(int i=0;i<n;i++){ ss[s[i]-'a']++; if(i>=m) ss[s[i-m]-'a']--; if(i>=m-1 && fun(ss,pp)) res.push_back(i-m+1); } return res; } bool fun(int ss[],int pp[]){ for(int i=0;i<26;i++){ if(ss[i]!=pp[i]) return false; } return true; } };
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> res=new ArrayList<>(); int n=s.length(); int m=p.length(); int[] ss=new int[26]; int[] pp=new int[26]; for(int i=0;i<m;i++) pp[p.charAt(i)-'a']++; for(int i=0;i<n;i++){ ss[s.charAt(i)-'a']++; if(i>=m) ss[s.charAt(i-m)-'a']--; if(i>=m-1 && fun(ss,pp)) res.add(i-m+1); } return res; } public static boolean fun(int[] ss,int[] pp){ for(int i=0;i<26;i++){ if(ss[i]!=pp[i]) return false; } return true; } }
4.子串
4.1 和为K的子串
代码实现（C++/Java）
class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int,int> map; map[0]=1; int sum=0,res=0; for(int x:nums){ sum+=x; if(map.count(sum-k)){ res+=map[sum-k]; } map[sum]++; } return res; } };
class Solution { public int subarraySum(int[] nums, int k) { Map<Integer,Integer> map=new HashMap<>(); map.put(0,1); int sum=0,res=0; for(int i=0;i<nums.length;i++){ sum+=nums[i]; if(map.containsKey(sum-k)){ res+=map.get(sum-k); } map.put(sum,map.getOrDefault(sum,0)+1); } return res; } }
4.2 滑动窗口最大值
代码实现（C++/Java）
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> res; int n=nums.size(); deque<int> q; //单调递减队列 for(int i=0;i<n;i++){ if(!q.empty() && q.front()<=i-k){ q.pop_front(); } while(!q.empty() && nums[i]>=nums[q.back()]){ q.pop_back(); } q.push_back(i); if(i>=k-1) res.push_back(nums[q.front()]); } return res; } };
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n=nums.length; int []res=new int[n-k+1]; Deque<Integer> q=new ArrayDeque<>(); int cnt=0; for(int i=0;i<nums.length;i++){ if(!q.isEmpty() && q.peekFirst()<=i-k){ q.pollFirst(); } while(!q.isEmpty() && nums[i]>nums[q.peekLast()]){ q.pollLast(); } q.offer(i); if(i>=k-1) res[cnt++]=nums[q.peekFirst()]; } return res; } }
4.3 最小覆盖子串
代码实现（C++/Java）
class Solution { public: string minWindow(string s, string t) { int len=0x3f3f3f3f; int cur=0;//结果字符串左端点 unordered_map<char,int>win,need; for(char c:t) need[c]++; int l=0,r=0; int cnt=0; while(r<s.size()){ char c=s[r++]; if(need.count(c)){ win[c]++; if(win[c]==need[c])cnt++; } //开始收缩 while(cnt==need.size()){ if(r-l<len){ len=r-l; cur=l; } c=s[l++]; if(need.count(c)){ if(win[c]==need[c]) cnt--; win[c]--; } } } return len==0x3f3f3f3f?"":s.substr(cur,len); } };
class Solution { public String minWindow(String s, String t) { Map<Character,Integer> need=new HashMap<>(); Map<Character,Integer> win=new HashMap<>(); for(char c:t.toCharArray()){ need.put(c,need.getOrDefault(c,0)+1); } int len=0x3f3f3f3f; int cur=0; int l=0,r=0; int cnt=0; while(r<s.length()){ char c=s.charAt(r); r++; if(need.containsKey(c)){ win.put(c,win.getOrDefault(c,0)+1); if(win.get(c).intValue()==need.get(c).intValue()) cnt++; } //收缩 while(cnt==need.size()){ if(r-l<len){ len=r-l; cur=l; } char d=s.charAt(l); l++; if(need.containsKey(d)){ if(win.get(d).intValue()==need.get(d).intValue()){ cnt--; } win.put(d,win.get(d).intValue()-1); } } } return len == 0x3f3f3f3f ? "" : s.substring(cur, cur + len); } }
5.普通数组
5.1 最大子数组和
代码实现（C++/Java）
class Solution { public: int maxSubArray(vector<int>& nums) { int n=nums.size(); vector<int> dp(n+10,0); dp[0]=nums[0]; for(int i=1;i<n;i++){ dp[i]=max(dp[i-1]+nums[i],nums[i]); } int res=-0x3f3f3f3f; for(int i=0;i<n;i++) res=max(res,dp[i]); return res; } };
class Solution { public: int maxSubArray(vector<int>& nums) { int res=-0x3f3f3f3f; int sum=0; for(int i=0;i<nums.size();i++){ sum+=nums[i]; if(sum>res){ res=sum; } if(sum<0) sum=0; } return res; } };
class Solution { public int maxSubArray(int[] nums) { int res=-0x3f3f3f3f; int sum=0; for(int i=0;i<nums.length;i++){ sum+=nums[i]; if(sum>res) res=sum; if(sum<0) sum=0; } return res; } }
5.2 合并区间
代码实现（C++/Java）
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(),intervals.end(),[](const vector<int> &a,vector<int> &b){ return a[0]<b[0]; }); vector<vector<int>> res; res.push_back(intervals[0]); for(int i=1;i<intervals.size();i++){ vector<int> &t=res.back(); if(intervals[i][0]<=t[1]){ t[1]=max(t[1],intervals[i][1]); }else { res.push_back(intervals[i]); } } return res; } };
class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals,new Comparator<int[]>(){ public int compare(int[] a,int[] b){ return Integer.compare(a[0],b[0]); } }); List<int[]> res=new ArrayList<>(); res.add(intervals[0]); for(int i=1;i<intervals.length;i++){ int[]t=res.get(res.size()-1); if(intervals[i][0]<=t[1]){ t[1]=Math.max(t[1],intervals[i][1]); } else { res.add(intervals[i]); } } int [][]result=new int[res.size()][2]; for(int i=0;i<res.size();i++){ for(int j=0;j<2;j++){ result[i][j]=res.get(i)[j]; } } return result; } }
5.3 旋转数组
代码实现（C++/Java）
class Solution { public: void rotate(vector<int>& nums, int k) { vector<int>arr(nums.size(),0); for(int i=0;i<nums.size();i++){ arr[(i+k)%nums.size()]=nums[i]; } for(int i=0;i<nums.size();i++){ nums[i]=arr[i]; } } };
class Solution { public void rotate(int[] nums, int k) { int[] arr=new int[nums.length]; for(int i=0;i<nums.length;i++){ arr[(i+k)%nums.length]=nums[i]; } for(int i=0;i<nums.length;i++){ nums[i]=arr[i]; } } }
5.4 除了自身以外数组的乘积
238. 除了自身以外数组的乘积 - 力扣（LeetCode）
代码实现（C++/Java）
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int> pre(n,1); vector<int> last(n,1); for(int i=1;i<n;i++){ pre[i]=pre[i-1]*nums[i-1]; } for(int i=n-2;i>=0;i--){ last[i]=last[i+1]*nums[i+1]; } vector<int> res(n); for(int i=0;i<n;i++){ res[i]=pre[i]*last[i]; } return res; } };
class Solution { public int[] productExceptSelf(int[] nums) { int n=nums.length; int[] pre=new int[n]; int[] last=new int[n]; Arrays.fill(pre,1); Arrays.fill(last,1); for(int i=1;i<n;i++){ pre[i]=pre[i-1]*nums[i-1]; } for(int i=n-2;i>=0;i--){ last[i]=last[i+1]*nums[i+1]; } int[] res=new int[n]; for(int i=0;i<n;i++){ res[i]=pre[i]*last[i]; } return res; } }
5.5 缺失的第一个正数
代码实现（C++/Java）
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n=nums.size(); for(int i=0;i<n;i++){ while(nums[i]>=1 && nums[i]<=n && nums[i]!=nums[nums[i]-1]){ swap(nums[i],nums[nums[i]-1]); } } for(int i=0;i<n;i++){ if(nums[i]!=i+1){ return i+1; } } return n+1; } };
class Solution { public int firstMissingPositive(int[] nums) { int n=nums.length; for(int i=0;i<n;i++){ while(nums[i]>=1 && nums[i]<=n && nums[i]!=nums[nums[i]-1]){ int idx=nums[i]-1; int t=nums[i]; nums[i]=nums[idx]; nums[idx]=t; } } for(int i=0;i<n;i++){ if(nums[i]!=i+1){ return i+1; } } return n+1; } }
6.矩阵
6.1 矩阵置零
代码实现（C++/Java）
class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m=matrix.size(); int n=matrix[0].size(); bool fRow=false; bool fCol=false; for(int i=0;i<m;i++){ if(matrix[i][0]==0){ fCol=true; break; } } for(int i=0;i<n;i++){ if(matrix[0][i]==0){ fRow=true; break; } } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(matrix[i][j]==0){ matrix[i][0]=0; matrix[0][j]=0; } } } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(matrix[i][0]==0 || matrix[0][j]==0){ matrix[i][j]=0; } } } if(fRow){ for(int i=0;i<n;i++){ matrix[0][i]=0; } } if(fCol){ for(int i=0;i<m;i++){ matrix[i][0]=0; } } } };
class Solution { public void setZeroes(int[][] matrix) { int m=matrix.length; int n=matrix[0].length; boolean fRow=false; boolean fCol=false; for(int i=0;i<m;i++){ if(matrix[i][0]==0){ fCol=true; break; } } for(int i=0;i<n;i++){ if(matrix[0][i]==0){ fRow=true; break; } } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(matrix[i][j]==0){ matrix[i][0]=0; matrix[0][j]=0; } } } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(matrix[i][0]==0 || matrix[0][j]==0){ matrix[i][j]=0; } } } if(fRow){ for(int i=0;i<n;i++){ matrix[0][i]=0; } } if(fCol){ for(int i=0;i<m;i++){ matrix[i][0]=0; } } } }
6.2 螺旋矩阵
代码实现（C++/Java）
class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { int m=matrix.size(); int n=matrix[0].size(); int l=0,r=n-1,t=0,b=m-1; vector<int> res; while(r>=l && b>=t){ for(int i=l;i<=r;i++){ res.push_back(matrix[t][i]); } t++; if(t>b) break; for(int i=t;i<=b;i++){ res.push_back(matrix[i][r]); } r--; if(l>r) break; for(int i=r;i>=l;i--){ res.push_back(matrix[b][i]); } b--; for(int i=b;i>=t;i--){ res.push_back(matrix[i][l]); } l++; } return res; } };
class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res=new ArrayList<>(); int m=matrix.length; int n=matrix[0].length; int l=0,r=n-1,t=0,b=m-1; while(r>=l && b>=t){ for(int i=l;i<=r;i++){ res.add(matrix[t][i]); } t++; if(t>b) break; for(int i=t;i<=b;i++){ res.add(matrix[i][r]); } r--; if(l>r) break; for(int i=r;i>=l;i--){ res.add(matrix[b][i]); } b--; for(int i=b;i>=t;i--){ res.add(matrix[i][l]); } l++; } return res; } }
6.3 旋转图像
代码实现（C++/Java）
class Solution { public: //先转置，再将每一行逆序 void rotate(vector<vector<int>>& matrix) { int n=matrix.size(); for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ swap(matrix[i][j],matrix[j][i]); } } for(int i=0;i<n;i++){ reverse(matrix[i].begin(),matrix[i].end()); } } };
class Solution { public void rotate(int[][] matrix) { int n=matrix.length; for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ int t=matrix[i][j]; matrix[i][j]=matrix[j][i]; matrix[j][i]=t; } } for(int i=0;i<n;i++){ int l=0,r=n-1; while(r>=l){ int t=matrix[i][l]; matrix[i][l]=matrix[i][r]; matrix[i][r]=t; l++; r--; } } } }
6.4 搜索二维矩阵2
代码实现（C++/Java）
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m=matrix.size(); int n=matrix[0].size(); if(m==0) return false; int x=0,y=n-1; while(y>=0 && x<m){ if(matrix[x][y]==target) return true; else if(matrix[x][y]>target) y--; else if(matrix[x][y]<target) x++; } return false; } };
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m=matrix.length; int n=matrix[0].length; int x=0,y=n-1; while(x<m && y>=0){ if(matrix[x][y]==target) return true; else if(matrix[x][y]>target) y--; else if(matrix[x][y]<target) x++; } return false; } }
7.链表
7.1 相交链表
代码实现（C++/Java）
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* pa=headA; ListNode* pb=headB; while(pa!=pb){ if(pa!=nullptr) pa=pa->next; else pa=headB; if(pb!=nullptr) pb=pb->next; else pb=headA; } return pa; } };
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pa=headA; ListNode pb=headB; while(pa!=pb){ if(pa!=null) pa=pa.next; else pa=headB; if(pb!=null) pb=pb.next; else pb=headA; } return pa; } }
7.2 反转链表
代码实现（C++/Java）
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pre=nullptr; ListNode* cur=head; while(cur!=nullptr){ ListNode* next=cur->next; cur->next=pre; pre=cur; cur=next; } return pre; } };
class Solution { public ListNode reverseList(ListNode head) { ListNode pre=null; ListNode cur=head; while(cur!=null){ ListNode next=cur.next; cur.next=pre; pre=cur; cur=next; } return pre; } }
7.3 回文链表
代码实现（C++/Java）
class Solution { public: bool isPalindrome(ListNode* head) { vector<int> arr; ListNode* cur=head; while(cur!=nullptr){ arr.push_back(cur->val); cur=cur->next; } int l=0,r=arr.size()-1; while(r>=l){ if(arr[l]!=arr[r])return false; l++; r--; } return true; } };
class Solution { public boolean isPalindrome(ListNode head) { ArrayList<Integer> list=new ArrayList<>(); ListNode cur=head; while(cur!=null){ list.add(cur.val); cur=cur.next; } int l=0,r=list.size()-1; while(r>=l){ if(list.get(l)!=list.get(r)) return false; l++; r--; } return true; } }
7.4 环形链表
代码实现（C++/Java）
class Solution { public: bool hasCycle(ListNode *head) { ListNode* fast=head; ListNode* slow=head; while(fast!=nullptr && fast->next!=nullptr){ fast=fast->next->next; slow=slow->next; if(fast==slow) return true; } return false; } };
public class Solution { public boolean hasCycle(ListNode head) { ListNode fast=head; ListNode slow=head; while(fast!=null && fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow) return true; } return false; } }
7.5 环形链表2
代码实现（C++/Java）
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast=head; ListNode* slow=head; while(fast!=nullptr && fast->next!=nullptr){ fast=fast->next->next; slow=slow->next; if(fast==slow){ ListNode* t1=head; ListNode* t2=fast; while(t1!=t2){ t1=t1->next; t2=t2->next; } return t1; } } return nullptr; } };
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast=head; ListNode slow=head; while(fast!=null && fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ ListNode t1=head; ListNode t2=fast; while(t1!=t2){ t1=t1.next; t2=t2.next; } return t1; } } return null; } }
7.6 合并两个有序链表
代码实现（C++/Java）
class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* dummy=new ListNode(-1); ListNode* cur=dummy; while(list1!=nullptr && list2!=nullptr){ if(list1->val<list2->val){ cur->next=list1; list1=list1->next; }else { cur->next=list2; list2=list2->next; } cur=cur->next; } if(list1!=nullptr) cur->next=list1; else if(list2!=nullptr) cur->next=list2; return dummy->next; } };
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy=new ListNode(-1); ListNode cur=dummy; while(list1!=null && list2!=null){ if(list1.val<list2.val){ cur.next=list1; list1=list1.next; } else { cur.next=list2; list2=list2.next; } cur=cur.next; } if(list1!=null) cur.next=list1; else if(list2!=null) cur.next=list2; return dummy.next; } }
7.7 两数相加
代码实现（C++/Java）
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummy=new ListNode(-1); ListNode* cur=dummy; int carry=0; while(l1!=nullptr || l2!=nullptr || carry!=0){ int sum=carry; if(l1!=nullptr){ sum+=l1->val; l1=l1->next; } if(l2!=nullptr){ sum+=l2->val; l2=l2->next; } carry=sum/10; cur->next=new ListNode(sum%10); cur=cur->next; } return dummy->next; } };
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy=new ListNode(-1); ListNode cur=dummy; int carry=0; while(l1!=null || l2!=null ||carry!=0){ int sum=carry; if(l1!=null){ sum+=l1.val; l1=l1.next; } if(l2!=null){ sum+=l2.val; l2=l2.next; } carry=sum/10; cur.next=new ListNode(sum%10); cur=cur.next; } return dummy.next; } }
7.8 删除链表的倒数第N个结点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
代码实现（C++/Java）
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy=new ListNode(-1); dummy->next=head; ListNode* fast=dummy; ListNode* slow=dummy; for(int i=1;i<=n+1;i++) fast=fast->next; while(fast!=nullptr){ fast=fast->next; slow=slow->next; } slow->next=slow->next->next; return dummy->next; } };
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy=new ListNode(-1); dummy.next=head; ListNode fast=dummy; ListNode slow=dummy; for(int i=1;i<=n+1;i++) fast=fast.next; while(fast!=null){ fast=fast.next; slow=slow.next; } slow.next=slow.next.next; return dummy.next; } }
7.9 两两交换链表中的节点
代码实现（C++/Java）
class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummy=new ListNode(0); dummy->next=head; ListNode* cur=dummy; while(cur->next!=nullptr && cur->next->next!=nullptr){ ListNode* t1=cur->next; ListNode* t2=cur->next->next->next; cur->next=cur->next->next; cur->next->next=t1; cur->next->next->next=t2; cur=cur->next->next; } return dummy->next; } };
class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy=new ListNode(-1); dummy.next=head; ListNode cur=dummy; while(cur.next!=null && cur.next.next!=null){ ListNode t1=cur.next; ListNode t2=cur.next.next.next; cur.next=cur.next.next; cur.next.next=t1; cur.next.next.next=t2; cur=cur.next.next; } return dummy.next; } }
7.10 K个一组反转链表
代码实现（C++/Java）
class Solution { public: ListNode* reverse(ListNode* head){ ListNode* pre=nullptr; ListNode* cur=head; while(cur!=nullptr){ ListNode* next=cur->next; cur->next=pre; pre=cur; cur=next; } return pre; } ListNode* reverseKGroup(ListNode* head, int k) { ListNode* dummy=new ListNode(-1); dummy->next=head; ListNode* pre=dummy; ListNode* end=dummy; while(end->next!=nullptr){ for(int i=0;i<k && end!=nullptr;i++){ end=end->next; } if(end==nullptr) break; //分组翻转 ListNode* start=pre->next; ListNode* next=end->next; end->next=nullptr; pre->next=reverse(start); start->next=next; pre=start; end=pre; } return dummy->next; } };
class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy=new ListNode(-1); dummy.next=head; ListNode pre=dummy; ListNode end=dummy; while(end.next!=null){ for(int i=0;i<k && end!=null;i++){ end=end.next; } if(end==null) break; ListNode start=pre.next; ListNode next=end.next; end.next=null; pre.next=reverse(start); start.next=next; pre=start; end=pre; } return dummy.next; } public static ListNode reverse(ListNode head){ ListNode pre=null; ListNode cur=head; while(cur!=null){ ListNode next=cur.next; cur.next=pre; pre=cur; cur=next; } return pre; } }
7.11 随机链表的复制
代码实现（C++/Java）
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { //创建新节点 k原节点->v新节点 unordered_map<Node*,Node*> map; Node* cur=head; while(cur!=nullptr){ map[cur]=new Node(cur->val); cur=cur->next; } //补充节点元素 cur=head; while(cur!=nullptr){ map[cur]->next=map[cur->next]; map[cur]->random=map[cur->random]; cur=cur->next; } return map[head]; } };
/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { //创建新节点 k原节点->v新节点 Map<Node,Node> map=new HashMap<>(); Node cur=head; 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); } }
7.12 排序链表
代码实现（C++/Java）
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { if(head==nullptr || head->next==nullptr) return head; ListNode* slow=head; ListNode* fast=head->next; while(fast!=nullptr && fast->next!=nullptr){ fast=fast->next->next; slow=slow->next; } ListNode* mid=slow->next; slow->next=nullptr; ListNode* l=sortList(head); ListNode* r=sortList(mid); return merge(l,r); } ListNode* merge(ListNode* l,ListNode* r){ ListNode* dummy=new ListNode(-1); ListNode* cur=dummy; while(l!=nullptr && r!=nullptr){ if(l->val<r->val){ cur->next=l; l=l->next; }else{ cur->next=r; r=r->next; } cur=cur->next; } if(l!=nullptr) cur->next=l; else if(r!=nullptr) cur->next=r; return dummy->next; } };
class Solution { public ListNode sortList(ListNode head) { if(head==null || head.next==null) return head; ListNode slow=head; ListNode fast=head.next; while(fast!=null && fast.next!=null){ fast=fast.next.next; slow=slow.next; } ListNode mid=slow.next; slow.next=null; ListNode l=sortList(head); ListNode r=sortList(mid); return merge(l,r); } public static ListNode merge(ListNode l,ListNode r){ ListNode dummy=new ListNode(0); ListNode cur=dummy; while(l!=null && r!=null){ if(l.val<r.val){ cur.next=l; l=l.next; }else { cur.next=r; r=r.next; } cur=cur.next; } if(l!=null) cur.next=l; else if(r!=null) cur.next=r; return dummy.next; } }
7.13 合并K个升序链表
代码实现（C++/Java）
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size()==0 || lists.empty()) return nullptr; return divide(lists,0,lists.size()-1); } ListNode* divide(vector<ListNode*>& lists,int l,int r){ if(l==r) return lists[l]; int mid=l+(r-l)/2; ListNode* left=divide(lists,l,mid); ListNode* right=divide(lists,mid+1,r); return merge(left,right); } ListNode* merge(ListNode* l,ListNode* r){ ListNode* dummy=new ListNode(-1); ListNode* cur=dummy; while(l!=nullptr && r!=nullptr){ if(l->val<r->val){ cur->next=l; l=l->next; }else { cur->next=r; r=r->next; } cur=cur->next; } if(l!=nullptr) cur->next=l; else if(r!=nullptr) cur->next=r; return dummy->next; } };
class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists==null || lists.length==0) return null; ListNode res=divide(lists,0,lists.length-1); return res; } public static ListNode divide(ListNode[]lists,int l,int r){ if(l==r) return lists[l]; int mid=l+(r-l)/2; ListNode left=divide(lists,l,mid); ListNode right=divide(lists,mid+1,r); return merge(left,right); } public static ListNode merge(ListNode l,ListNode r){ ListNode dummy=new ListNode(-1); ListNode cur=dummy; while(l!=null && r!=null){ if(l.val<r.val){ cur.next=l; l=l.next; }else { cur.next=r; r=r.next; } cur=cur.next; } if(l!=null) cur.next=l; else if(r!=null) cur.next=r; return dummy.next; } }
7.14 LRU缓存
代码实现（C++/Java）
// 定义双向链表节点 struct DLinkedNode { int key; int value; DLinkedNode* prev; DLinkedNode* next; // 构造函数 DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {} }; class LRUCache { private: unordered_map<int, DLinkedNode*> cache; // 哈希表：key -> 节点 DLinkedNode* head; // 虚拟头节点（最近使用） DLinkedNode* tail; // 虚拟尾节点（最久未使用） int size; // 当前缓存大小 int capacity; // 缓存容量 // 辅助函数：将节点移到链表头部（标记为最近使用） void moveToHead(DLinkedNode* node) { // 先移除节点 removeNode(node); // 再插入到头部 addToHead(node); } // 辅助函数：移除指定节点 void removeNode(DLinkedNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } // 辅助函数：将节点插入到虚拟头节点之后 void addToHead(DLinkedNode* node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } // 辅助函数：移除虚拟尾节点的前一个节点（最久未使用），并返回该节点 DLinkedNode* removeTail() { DLinkedNode* node = tail->prev; removeNode(node); return node; } public: // 初始化LRU缓存 LRUCache(int _capacity) : capacity(_capacity), size(0) { // 创建虚拟头、尾节点，避免空指针处理 head = new DLinkedNode(); tail = new DLinkedNode(); head->next = tail; tail->prev = head; } // 获取key对应的值，不存在返回-1 int get(int key) { // key不存在 if (!cache.count(key)) { return -1; } // key存在，找到节点并移到头部 DLinkedNode* node = cache[key]; moveToHead(node); return node->value; } // 插入/更新key-value void put(int key, int value) { // key不存在 if (!cache.count(key)) { // 创建新节点 DLinkedNode* node = new DLinkedNode(key, value); // 加入哈希表 cache[key] = node; // 插入到链表头部 addToHead(node); size++; // 缓存已满，移除最久未使用的节点 if (size > capacity) { DLinkedNode* removedNode = removeTail(); // 从哈希表中删除 cache.erase(removedNode->key); // 释放内存（可选，OJ平台不要求但规范） delete removedNode; size--; } } else { // key存在，更新值并移到头部 DLinkedNode* node = cache[key]; node->value = value; moveToHead(node); } } // 析构函数（可选，释放内存） ~LRUCache() { DLinkedNode* cur = head; while (cur != nullptr) { DLinkedNode* next = cur->next; delete cur; cur = next; } } };
// 双向链表节点 class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; // 无参构造（创建虚拟头/尾节点） public DLinkedNode() {} // 带参构造（创建缓存节点） public DLinkedNode(int key, int value) { this.key = key; this.value = value; } } class LRUCache { private final Map<Integer, DLinkedNode> cache; // 哈希表：key -> 节点 private final DLinkedNode head; // 虚拟头（最近使用） private final DLinkedNode tail; // 虚拟尾（最久未使用） private final int capacity; private int size; // 当前缓存大小 public LRUCache(int capacity) { this.capacity = capacity; this.size = 0; this.cache = new HashMap<>(); // 初始化虚拟头/尾节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } // 获取key对应的值 public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } // 访问后移到头部（标记为最近使用） moveToHead(node); return node.value; } // 插入/更新key-value public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { // 新建节点 DLinkedNode newNode = new DLinkedNode(key, value); cache.put(key, newNode); // 插入到头部 addToHead(newNode); size++; // 超过容量，移除最久未使用的节点（尾节点前一个） if (size > capacity) { DLinkedNode removedNode = removeTail(); cache.remove(removedNode.key); size--; } } else { // 更新值并移到头部 node.value = value; moveToHead(node); } } // 辅助：将节点插入到虚拟头之后 private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } // 辅助：移除指定节点 private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } // 辅助：将节点移到头部（先移除，再插入） private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } // 辅助：移除虚拟尾节点的前一个节点（最久未使用） private DLinkedNode removeTail() { DLinkedNode node = tail.prev; removeNode(node); return node; } }
8.二叉树
8.1 二叉树中序遍历
代码实现（C++/Java）
class Solution { public: void midOrder(TreeNode* node,vector<int>& res){ if(node==nullptr) return; midOrder(node->left,res); res.push_back(node->val); midOrder(node->right,res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; midOrder(root,res); return res; } };
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; TreeNode* cur=root; while(cur!=nullptr || !stk.empty()){ if(cur!=nullptr){ stk.push(cur); cur=cur->left; }else { cur=stk.top(); stk.pop(); res.push_back(cur->val); cur=cur->right; } } return res; } };
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res=new ArrayList<>(); Stack<TreeNode> stk=new Stack<>(); TreeNode cur=root; while(cur!=null || !stk.isEmpty()){ if(cur!=null){ stk.push(cur); cur=cur.left; }else{ cur=stk.pop(); res.add(cur.val); cur=cur.right; } } return res; } }
8.2 二叉树的最大深度
代码实现（C++/Java）
class Solution { public: int maxDepth(TreeNode* root) { if(root==nullptr) return 0; int l=maxDepth(root->left); int r=maxDepth(root->right); int res=max(l,r)+1; return res; } };
class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0; int l=maxDepth(root.left); int r=maxDepth(root.right); int res=Math.max(l,r)+1; return res; } }
8.3 翻转二叉树
代码实现（C++/Java）
class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==nullptr) return nullptr; swap(root->left,root->right); invertTree(root->left); invertTree(root->right); return root; } };
class Solution { public TreeNode invertTree(TreeNode root) { if(root==null) return null; TreeNode t=root.left; root.left=root.right; root.right=t; invertTree(root.left); invertTree(root.right); return root; } }
8.4 对称二叉树
代码实现（C++/Java）
class Solution { public: bool cp(TreeNode* l,TreeNode* r){ if(l==nullptr && r==nullptr) return true; else if(l==nullptr && r!=nullptr) return false; else if(l!=nullptr && r==nullptr) return false; else if(l->val!=r->val) return false; else return cp(l->left,r->right) && cp(l->right,r->left); } bool isSymmetric(TreeNode* root) { if(root==nullptr) return true; return cp(root->left,root->right); } };
class Solution { public boolean isSymmetric(TreeNode root) { if(root==null) return true; return cp(root.left,root.right); } public static boolean cp(TreeNode l,TreeNode r){ if(l==null && r==null) return true; else if(l==null && r!=null) return false; else if(l!=null && r==null) return false; else if(l.val!=r.val) return false; else return cp(l.left,r.right) && cp(l.right,r.left); } }
8.5 二叉树的直径
代码实现（C++/Java）
class Solution { public: int res=0; int dfs(TreeNode* node){ if(node==nullptr) return 0; int l=dfs(node->left); int r=dfs(node->right); res=max(res,l+r); return max(l,r)+1; } int diameterOfBinaryTree(TreeNode* root) { dfs(root); return res; } };
class Solution { int res=0; int dfs(TreeNode node){ if(node==null) return 0; int l=dfs(node.left); int r=dfs(node.right); res=Math.max(res,l+r); return Math.max(l,r)+1; } public int diameterOfBinaryTree(TreeNode root) { dfs(root); return res; } }
8.6 二叉树的层序遍历
代码实现（C++/Java）
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; queue<TreeNode*> q; if(root!=nullptr) q.push(root); while(!q.empty()){ int size=q.size(); vector<int> level; for(int i=1;i<=size;i++){ TreeNode* node=q.front(); q.pop(); level.push_back(node->val); if(node->left!=nullptr) q.push(node->left); if(node->right!=nullptr) q.push(node->right); } res.push_back(level); } return res; } };
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res=new ArrayList<>(); Queue<TreeNode> q=new LinkedList<>(); if(root!=null) q.offer(root); while(!q.isEmpty()){ int size=q.size(); ArrayList<Integer> level=new ArrayList<>(); for(int i=1;i<=size;i++){ TreeNode node=q.poll(); level.add(node.val); if(node.left!=null) q.offer(node.left); if(node.right!=null) q.offer(node.right); } res.add(level); } return res; } }
8.7 将有序数组转为二叉搜索树
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
代码实现（C++/Java）
class Solution { public: //二叉搜索树保证中序遍历有序 TreeNode* build(vector<int> &nums,int l,int r){ if(l>r) return nullptr; int mid=l+((r-l)>>1); TreeNode* node=new TreeNode(nums[mid]); node->left=build(nums,l,mid-1); node->right=build(nums,mid+1,r); return node; } TreeNode* sortedArrayToBST(vector<int>& nums) { return build(nums,0,nums.size()-1); } };
class Solution { //二叉搜索树保证中序遍历有序 public TreeNode sortedArrayToBST(int[] nums) { return build(nums,0,nums.length-1); } public static TreeNode build(int[]nums,int l,int r){ if(l>r) return null; int mid=l+((r-l)>>1); TreeNode node=new TreeNode(nums[mid]); node.left=build(nums,l,mid-1); node.right=build(nums,mid+1,r); return node; } }
8.8 验证二叉搜索树
代码实现（C++/Java）
typedef long long ll; class Solution { public: bool cp(TreeNode* node,ll l,ll r){ if(node==nullptr) return true; if(node->val<=l || node->val>=r) return false; //左子树小于当前值，右子树大于当前值 return cp(node->left,l,node->val) && cp(node->right,node->val,r); } bool isValidBST(TreeNode* root) { return cp(root,LLONG_MIN,LLONG_MAX); } };
class Solution { public boolean isValidBST(TreeNode root) { return cp(root,Long.MIN_VALUE,Long.MAX_VALUE); } public static boolean cp(TreeNode node,long l,long r){ if(node==null) return true; else if(node.val<=l || node.val>=r) return false; return cp(node.left,l,node.val) && cp(node.right,node.val,r); } }
8.9 二叉搜索树中第K小的元素
230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）
代码实现（C++/Java）
class Solution { public: int cnt,res,kv; void midOrder(TreeNode* node){ if(node==nullptr) return; midOrder(node->left); cnt++; if(cnt==kv){ res=node->val; return; } midOrder(node->right); } int kthSmallest(TreeNode* root, int k) { cnt=0; kv=k; midOrder(root); return res; } };
class Solution { public static int cnt,res,kv; public int kthSmallest(TreeNode root, int k) { cnt=0; kv=k; midOrder(root); return res; } public static void midOrder(TreeNode node){ if(node==null) return; midOrder(node.left); cnt++; if(cnt==kv){ res=node.val; return; } midOrder(node.right); } }
8.10 二叉树的右视图
代码实现（C++/Java）
class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> res; if(root==nullptr) return res; queue<TreeNode*> q; q.push(root); while(!q.empty()){ int size=q.size(); for(int i=1;i<=size;i++){ TreeNode* node=q.front(); q.pop(); if(i==size) res.push_back(node->val); if(node->left!=nullptr) q.push(node->left); if(node->right!=nullptr) q.push(node->right); } } return res; } };
class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> res=new ArrayList<>(); if(root==null) return res; Queue<TreeNode> q=new LinkedList<>(); q.offer(root); while(!q.isEmpty()){ int size=q.size(); for(int i=1;i<=size;i++){ TreeNode node=q.poll(); if(i==size) res.add(node.val); if(node.left!=null) q.offer(node.left); if(node.right!=null) q.offer(node.right); } } return res; } }
8.11 二叉树展开为链表
代码实现（C++/Java）
class Solution { public: void preOrder(TreeNode* node,vector<TreeNode*>& res){ if(node==nullptr) return; res.push_back(node); preOrder(node->left,res); preOrder(node->right,res); } void flatten(TreeNode* root) { vector<TreeNode*> res; preOrder(root,res); int n=res.size(); for(int i=1;i<n;i++){ TreeNode* pre=res.at(i-1); TreeNode* cur=res.at(i); pre->left=nullptr; pre->right=cur; } } };
class Solution { public void flatten(TreeNode root) { ArrayList<TreeNode> res=new ArrayList<>(); preOrder(root,res); int n=res.size(); for(int i=1;i<n;i++){ TreeNode pre=res.get(i-1); TreeNode cur=res.get(i); pre.left=null; pre.right=cur; } } public static void preOrder(TreeNode node,ArrayList<TreeNode> res){ if(node==null) return; res.add(node); preOrder(node.left,res); preOrder(node.right,res); } }
8.12 从前序与中序遍历序列造二叉树
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
代码实现（C++/Java）
class Solution { public: //中序的值->索引 unordered_map<int,int> map; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { for(int i=0;i<inorder.size();i++){ map[inorder[i]]=i; } return build(preorder,0,preorder.size()-1, inorder,0,inorder.size()-1); } TreeNode* build(vector<int>& preorder,int pl,int pr, vector<int>& inorder,int il,int ir){ if(pl>pr || il>ir){ return nullptr; } //根节点 int rootVal=preorder[pl]; TreeNode* root=new TreeNode(rootVal); //根节点在中序数组中的索引 int rootIdx=map[rootVal]; //左子树的节点数量 int lcnt=rootIdx-il; //左子树 root->left=build(preorder,pl+1,pl+lcnt, inorder,il,rootIdx-1); //右子树 root->right=build(preorder,pl+lcnt+1,pr, inorder,rootIdx+1,ir); return root; } };
class Solution { public static Map<Integer,Integer> map; public TreeNode buildTree(int[] preorder, int[] inorder) { map=new HashMap<>(); for(int i=0;i<inorder.length;i++){ map.put(inorder[i],i); } return build(preorder,0,preorder.length-1, inorder,0,inorder.length-1); } public static TreeNode build(int[]preorder,int pl,int pr, int[]inorder,int il,int ir){ if(pl>pr || il>ir) return null; //根节点 int rootVal=preorder[pl]; TreeNode root=new TreeNode(rootVal); int rootIdx=map.get(rootVal); int lcnt=rootIdx-il; //左子树 root.left=build(preorder,pl+1,pl+lcnt, inorder,il,rootIdx-1); //右子树 root.right=build(preorder,pl+lcnt+1,pr, inorder,rootIdx+1,ir); return root; } }
8.13 路径总和3
代码实现（C++/Java）
class Solution { public: int dfs(TreeNode* node,long long targetSum){ if(node==nullptr) return 0; int cnt=0; if(node->val==targetSum){ cnt++; } cnt+=dfs(node->left,targetSum-node->val); cnt+=dfs(node->right,targetSum-node->val); return cnt; } int pathSum(TreeNode* root, int targetSum) { if(root==nullptr) return 0; int res=dfs(root,targetSum); res+=pathSum(root->left,targetSum); res+=pathSum(root->right,targetSum); return res; } };
class Solution { public int pathSum(TreeNode root, int targetSum) { if(root==null) return 0; int res=dfs(root,targetSum); res+=pathSum(root.left,targetSum); res+=pathSum(root.right,targetSum); return res; } public static int dfs(TreeNode node,long targetSum){ if(node==null) return 0; int cnt=0; if(node.val==targetSum) cnt++; cnt+=dfs(node.left,targetSum-node.val); cnt+=dfs(node.right,targetSum-node.val); return cnt; } }
8.14 二叉树的最近公共祖先
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
代码实现（C++/Java）
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==nullptr) return nullptr; if(root==p || root==q) return root; TreeNode* l=lowestCommonAncestor(root->left,p,q); TreeNode* r=lowestCommonAncestor(root->right,p,q); if(l!=nullptr && r!=nullptr){ return root; }else if(l==nullptr){ return r; }else { return l; } } };
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null) return null; if(root==p || root==q) return root; TreeNode l=lowestCommonAncestor(root.left,p,q); TreeNode r=lowestCommonAncestor(root.right,p,q); if(l!=null && r!=null){ return root; }else if(l==null){ return r; }else { return l; } } }
8.15 二叉树中的最大路径和
124. 二叉树中的最大路径和 - 力扣（LeetCode）
代码实现（C++/Java）
const int MIN=-0x3f3f3f3f; class Solution { public: int res=MIN; //以root为根节点的单边最大贡献值 int dfs(TreeNode* root){ if(root==nullptr) return 0; int l=max(dfs(root->left),0); int r=max(dfs(root->right),0); //以当前节点为最高点的最大路径和 int cur=root->val+l+r; res=max(res,cur); return root->val+max(l,r); } int maxPathSum(TreeNode* root) { dfs(root); return res; } };
class Solution { public static int res; public int maxPathSum(TreeNode root) { res=-0x3f3f3f3f; dfs(root); return res; } public static int dfs(TreeNode root){ if(root==null) return 0; int l=Math.max(dfs(root.left),0); int r=Math.max(dfs(root.right),0); int cur=root.val+l+r; res=Math.max(res,cur); return root.val+Math.max(l,r); } }
