Leetcode刷题面试2025

文章目录

- - 排序算法
  - 动态规划
  - 回溯算法
  - 贪心算法
  - 位运算
  - 数学题
  - 二分查找
  - 数组
  - 链表
  - 栈
  - 队列
  - 双指针
  - 哈希表
  - 前缀和
  - 二叉树

以下是为你整理的上述 LeetCode 题目对应的链接：

排序算法

插入排序

public class InsertionSort {public static void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i]; // 当前需要插入的元素int j = i - 1;// 将比 key 大的元素向后移动while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key; // 插入 key 到正确位置}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6};insertionSort(arr);System.out.println("排序后的数组:");for (int i : arr) {System.out.print(i + " ");}}
}

冒泡排序

public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}// 如果没有发生交换，说明数组已经有序，提前退出if (!swapped) {break;}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println("排序后的数组:");for (int i : arr) {System.out.print(i + " ");}}
}

快速排序

public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {// 找到分区点，将数组分为两部分int pi = partition(arr, low, high);// 递归排序左半部分quickSort(arr, low, pi - 1);// 递归排序右半部分quickSort(arr, pi + 1, high);}}// 分区函数private static int partition(int[] arr, int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1; // i 是较小元素的索引for (int j = low; j < high; j++) {// 如果当前元素小于或等于基准if (arr[j] <= pivot) {i++;// 交换 arr[i] 和 arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将基准元素放到正确的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1; // 返回基准元素的索引}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);System.out.println("排序后的数组:");for (int i : arr) {System.out.print(i + " ");}}
}

堆排序

public class HeapSort {public static void heapSort(int[] arr) {int n = arr.length;// 构建最大堆（从最后一个非叶子节点开始）for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐个提取堆顶元素（最大值），放到数组末尾for (int i = n - 1; i > 0; i--) {// 将堆顶元素（最大值）与当前末尾元素交换int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 重新调整堆，使其满足最大堆性质heapify(arr, i, 0);}}// 堆化函数：调整以 i 为根的子树为最大堆private static void heapify(int[] arr, int n, int i) {int largest = i; // 初始化最大值为根节点int left = 2 * i + 1; // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点比根节点大，更新最大值if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点比当前最大值大，更新最大值if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是根节点，交换并递归调整if (largest != i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;// 递归调整受影响的子树heapify(arr, n, largest);}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6, 7};heapSort(arr);System.out.println("排序后的数组:");for (int i : arr) {System.out.print(i + " ");}}
}

计数排序

public class CountingSort { public static void countingSort(int[] arr) { if (arr == null || arr.length  <= 1) { return; } // 找出数组中的最大值 int max = arr[0]; for (int num : arr) { if (num > max) { max = num; } } // 定义计数数组，长度为最大值 + 1 int[] count = new int[max + 1]; // 统计每个元素出现的次数 for (int num : arr) { count[num]++; } // 遍历计数数组，将元素按顺序放回原数组 int index = 0; for (int i = 0; i < count.length;  i++) { while (count[i] > 0) { arr[index++] = i; count[i]--; } } } public static void main(String[] args) { int[] arr = {4, 2, 2, 8, 3, 3, 1}; System.out.println(" 排序前:"); for (int num : arr) { System.out.print(num  + " "); } // 调用计数排序方法 countingSort(arr); System.out.println("\n 排序后:"); for (int num : arr) { System.out.print(num  + " "); } } 
}

桶排序

import java.util.ArrayList;  
import java.util.Collections;  
import java.util.List;  public class BucketSort { public static double[] bucketSort(double[] array) { if (array == null || array.length  == 0) { return array; } // 找出数组中的最大值和最小值 double max = array[0]; double min = array[0]; for (double num : array) { if (num > max) { max = num; } if (num < min) { min = num; } } // 计算桶的数量 int bucketNum = array.length;  List<List<Double>> buckets = new ArrayList<>(); for (int i = 0; i < bucketNum; i++) { buckets.add(new  ArrayList<>()); } // 将元素分配到不同的桶中 for (double num : array) { int bucketIndex = (int) ((num - min) * (bucketNum - 1) / (max - min)); buckets.get(bucketIndex).add(num);  } // 对每个桶内的元素进行排序 for (List<Double> bucket : buckets) { Collections.sort(bucket);  } // 将所有桶中的元素合并到一个数组中 double[] sortedArray = new double[array.length]; int index = 0; for (List<Double> bucket : buckets) { for (double num : bucket) { sortedArray[index++] = num; } } return sortedArray; } public static void main(String[] args) { double[] array = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51}; double[] sortedArray = bucketSort(array); for (double num : sortedArray) { System.out.print(num  + " "); } } 
}

动态规划

爬楼梯（LeetCode 70）

    public int climbStairs(int n) {if (n <= 2) {return n;}int first = 1;int second = 2;int result = 0;for (int i = 3; i <= n; i++) {result = first + second;first = second;second = result;}return result;}
}

零钱兑换（LeetCode 322）

    public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];Arrays.fill(dp, amount+1);dp[0] = 0;for (int i = 1; i <= amount; i++) {for(int coin : coins) {if (coin <= i) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}

买卖股票的最佳时机（LeetCode 121）

    public int maxProfit(int[] prices) {int minPrice = Integer.MAX_VALUE;int maxProfit = 0;for (int price : prices) {if (price < minPrice) {minPrice = price;} else if (price - minPrice > maxProfit) {maxProfit = price - minPrice;}}return maxProfit;}

买卖股票的最佳时机 II（LeetCode 122）

   public int maxProfit(int[] prices) {int profit = 0;for (int i = 1; i < prices.length; i++) {int pr = prices[i] - prices[i - 1]if (pr > 0) {profit += pr;}}return profit;}

最长上升子序列（LeetCode 300）

    public int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int[] dp = new int[nums.length];Arrays.fill(dp, 1);int max = 1;for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}max = Math.max(max, dp[i]);}}return max;}

不同路径（LeetCode 62）

    public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for (int i = 0; i < m; i++) {dp[i][0] = 1;}for (int i = 0; i < n; i++) {dp[0][i] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}

最小路径和（LeetCode 64）

    public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];dp[0][0] = grid[0][0];for (int i = 1; i < n; i++) {dp[0][i] = dp[0][i - 1] + grid[0][i];}for (int i = 1; i < m; i++) {dp[i][0] = dp[i - 1][0] + grid[i][0]; }for (int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];}}return dp[m - 1][n - 1];}

打家劫舍（LeetCode 198）

    public int rob(int[] nums) {int n = nums.length;if (n == 0) return 0;if (n == 1) return nums[0];int[] dp = new int[n];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < n; i++) {dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);}return dp[n - 1];}

打家劫舍 II（LeetCode 213）

    public int rob(int[] nums) {int n = nums.length;if (n == 0) {return 0;}if (n == 1) {return nums[0];}// Case 1: Rob houses from the first to the second - last houseint result1 = robRange(nums, 0, n - 2);// Case 2: Rob houses from the second to the last houseint result2 = robRange(nums, 1, n - 1);// Return the maximum of the two resultsreturn Math.max(result1, result2);}private int robRange(int[] nums, int start, int end) {if (start == end) {return nums[start];}int n = end - start + 1;int[] dp = new int[n];dp[0] = nums[start];dp[1] = Math.max(nums[start], nums[start + 1]);for (int i = 2; i < n; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);}return dp[n - 1];}

零钱兑换 II（LeetCode 518）

   public int change(int amount, int[] coins) {// Create a dp array to store the number of combinations for each amountint[] dp = new int[amount + 1];// Initialize dp[0] to 1, as there is one way to make up amount 0 (using no coins)dp[0] = 1;// Iterate through each coin denominationfor (int coin : coins) {// Update the dp array for each amount from coin to the target amountfor (int i = coin; i <= amount; i++) {// The number of combinations to make up amount i is the sum of the original number of combinations// and the number of combinations to make up amount i - coindp[i] += dp[i - coin];}}// Return the number of combinations to make up the target amountreturn dp[amount];}

回溯算法

N 皇后（LeetCode 51）

    private List<List<String>> result = new ArrayList<>();private int n;public List<List<String>> solveNQueens(int n) {this.n = n;char[][] board = new char[n][n];// Initialize the chessboardfor (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {board[i][j] = '.';}}backtrack(board, 0);return result;}private void backtrack(char[][] board, int row) {if (row == n) {result.add(constructSolution(board));return;}for (int col = 0; col < n; col++) {if (isValid(board, row, col)) {board[row][col] = 'Q';backtrack(board, row + 1);board[row][col] = '.';}}}private boolean isValid(char[][] board, int row, int col) {// Check the columnfor (int i = 0; i < row; i++) {if (board[i][col] == 'Q') {return false;}}// Check the upper - left diagonalfor (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (board[i][j] == 'Q') {return false;}}// Check the upper - right diagonalfor (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (board[i][j] == 'Q') {return false;}}return true;}private List<String> constructSolution(char[][] board) {List<String> solution = new ArrayList<>();for (int i = 0; i < n; i++) {solution.add(new String(board[i]));}return solution;}

子集（LeetCode 78）

    public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> result = new ArrayList<>();track(result, new ArrayList<Integer>(), nums, 0);return result;}private void track(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {result.add(new ArrayList<>(tempList));for (int i = start; i < nums.length; i++) {tempList.add(nums[i]);track(result, tempList, nums, i + 1);tempList.remove(tempList.size() - 1);}}

全排列（LeetCode 46）

    List<List<Integer>> result;List<Integer> list;boolean[] used;int[] nums;public List<List<Integer>> permute(int[] nums) {this.result = new ArrayList<>();this.used = new boolean[nums.length];this.list = new ArrayList<>();this.nums = nums;track();return result;}private void track() {if (list.size() == nums.length) {result.add(new ArrayList<>(list));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) {continue;}used[i] = true;list.add(nums[i]);track();used[i] = false;list.remove(list.size() - 1);}}

组合（LeetCode 77）

    private List<List<Integer>> result;private List<Integer> temp;private int n;private int k;public List<List<Integer>> combine(int n, int k) {this.result = new ArrayList<>();this.temp = new ArrayList<>();this.n = n;this.k = k;track(1);return result;}private void track(int start) {if (temp.size() == k) {result.add(new ArrayList<>(temp));return;}for (int i = start; i <=n; i++) {temp.add(i);track(i+1);temp.remove(temp.size() - 1);}}

电话号码的字母组合（LeetCode 17）

    private static final String[] PHONE_MAP = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};private List<String> result;private StringBuilder sb;private String digits;public List<String> letterCombinations(String digits) {this.result = new ArrayList<>();this.sb = new StringBuilder();this.digits = digits;if (digits == null || digits.length() == 0) {return result;}track(0);return result;}private void track(int index) {if (index == digits.length()) {result.add(sb.toString());return;}int digit = digits.charAt(index) - '0';String letters = PHONE_MAP[digit];for (int i = 0; i < letters.length(); i++) {sb.append(letters.charAt(i));track(index+1);sb.deleteCharAt(sb.length() - 1);}}

单词搜索（LeetCode 79）

    private boolean[][] visited;private int rows, cols;public boolean exist(char[][] board, String word) {rows = board.length;cols = board[0].length;visited = new boolean[rows][cols];for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == word.charAt(0) && backtrack(board, word, i, j, 0)) {return true;}}}return false;}private boolean backtrack(char[][] board, String word, int i, int j, int index) {if (index == word.length()) {return true;}if (i < 0 || i >= rows || j < 0 || j >= cols || visited[i][j] || board[i][j] != word.charAt(index)) {return false;}visited[i][j] = true;boolean found = backtrack(board, word, i + 1, j, index + 1) ||backtrack(board, word, i - 1, j, index + 1) ||backtrack(board, word, i, j + 1, index + 1) ||backtrack(board, word, i, j - 1, index + 1);visited[i][j] = false;return found;}

组合总和（LeetCode 39）

    public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();backtrack(result, new ArrayList<>(), candidates, target, 0);return result;}private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {if (remain < 0) {return;} else if (remain == 0) {result.add(new ArrayList<>(tempList));} else {for (int i = start; i < candidates.length; i++) {tempList.add(candidates[i]);backtrack(result, tempList, candidates, remain - candidates[i], i);tempList.remove(tempList.size() - 1);}}}

组合总和 II（LeetCode 40）

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(candidates);backtrack(result, new ArrayList<>(), candidates, target, 0);return result;}private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {if (remain < 0) {return;} else if (remain == 0) {result.add(new ArrayList<>(tempList));} else {for (int i = start; i < candidates.length; i++) {// Skip duplicatesif (i > start && candidates[i] == candidates[i - 1]) {continue;}tempList.add(candidates[i]);backtrack(result, tempList, candidates, remain - candidates[i], i + 1);tempList.remove(tempList.size() - 1);}}}

贪心算法

分发饼干（LeetCode 455）

    public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int nums = 0;int i = 0; int j = 0;while(i < g.length && j < s.length) {if (s[j] >= g[i]) {nums++;i++;}j++;}return nums;}

柠檬水找零（LeetCode 860）

    public boolean lemonadeChange(int[] bills) {int five = 0, ten = 0;for (int bill: bills) {switch(bill) {case 5:five++;break;case 10:if(five == 0) {return false;}five--;ten++;break;case 20:if(five>0&&ten>0) {five--;ten--;} else if(five >= 3) {five -= 3;} else {return false;}break;}}return true;}

最大子序和（LeetCode 53）

    public int maxSubArray(int[] nums) {int maxSoFar = nums[0];int maxEndHere = nums[0];for (int i = 1; i < nums.length; i++) {maxEndHere = Math.max(nums[i], maxEndHere + nums[i]);maxSoFar = Math.max(maxSoFar, maxEndHere);}return maxSoFar;}

买卖股票的最佳时机（LeetCode 121）

    public int maxProfit(int[] prices) {int minPrice = Integer.MAX_VALUE;int maxProfit = 0;for (int price : prices) {if (price < minPrice) {minPrice = price;} else if (price - minPrice > maxProfit) {maxProfit = price - minPrice;}}return maxProfit;}

跳跃游戏（LeetCode 55）

    public boolean canJump(int[] nums) {int lastPos = nums.length - 1;for (int i = nums.length - 1; i >= 0; i--) {if (i + nums[i] >= lastPos) {lastPos = i;}}return lastPos == 0;}

加油站（LeetCode 134）

    public int canCompleteCircuit(int[] gas, int[] cost) {int total = 0;int current = 0;int start = 0;for (int i = 0; i < gas.length; i++) {total += gas[i] - cost[i];current += gas[i] - cost[i];if (current < 0) {start = i + 1;current = 0;}}return total >= 0 ? start : -1;}

种花问题（LeetCode 605）

    public boolean canPlaceFlowers(int[] flowerbed, int n) {int count = 0;for (int i = 0; i < flowerbed.length; i++) {if (flowerbed[i] == 0&& (i == 0 || flowerbed[i - 1] == 0)&& (i == flowerbed.length - 1 || flowerbed[i+1] == 0)) {flowerbed[i] = 1;count++;}}return count >= n;}

位运算

只出现一次的数字（LeetCode 136）

    public int singleNumber(int[] nums) {int result = 0;for (int num: nums) {result ^= num;}return result;}

只出现一次的数字 II（LeetCode 137）

    public int singleNumber(int[] nums) {int ones = 0, twos = 0;for (int num : nums) {ones = (ones ^ num) & ~twos;twos = (twos ^ num) & ~ones;}return ones;}

只出现一次的数字 III（LeetCode 260）

    public int[] singleNumber(int[] nums) {// 第一步：对所有数字进行异或int xorResult = 0;for (int num : nums) {xorResult ^= num;  // xorResult 最终得到的是两个只出现一次的数字的异或结果}// 第二步：找到 xorResult 中最右边的 1int rightmostOne = xorResult & (-xorResult);  // 第三步：根据这个位将数组分成两组int x = 0;for (int num : nums) {if ((num & rightmostOne) != 0) {  // 如果当前数字在这个位上是 1x ^= num;  // 将其归入第一组并异或}}// 第四步：得到另一个数int y = xorResult ^ x;  // 用总异或结果异或第一个数，得到第二个数return new int[]{x, y};}

汉明距离（LeetCode 461）

    public int hammingDistance(int x, int y) {int xor = x ^ y;int distance = 0;while(xor != 0) {distance += xor & 1;xor >>= 1;}return distance;}

丢失的数字（LeetCode 268）

    public int missingNumber(int[] nums) {int xor = 0;for (int i = 0; i <= nums.length; i++) {xor ^= i;}for(int n : nums) {xor ^= n;}return xor;}

数学题

Pow(x, n)（LeetCode 50）

    public double myPow(double x, int n) {long N = n;return N >= 0 ? quickPow(x, N) : 1.0 / quickPow(x, -N);}private double quickPow(double x, long n) {double ans = 1.0;double current = x;while (n > 0) {if (n % 2 == 1) {ans *= current;}current *= current;n /= 2;}return ans;}

字符串相乘（LeetCode 43）

    public String multiply(String num1, String num2) {if (num1.equals("0") || num2.equals("0")) {return "0";}int m = num1.length();int n = num2.length();// 初始化结果数组int[] result = new int[m + n];for (int i = m - 1; i >= 0; i--) {for (int j = n - 1; j >= 0; j--) {// 计算当前位的乘积int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');// 计算乘积在结果数组中的位置int p1 = i + j;int p2 = i + j + 1;// 加上之前的进位int total = mul + result[p2];// 更新结果数组result[p2] = total % 10;result[p1] += total / 10;}}StringBuilder sb = new StringBuilder();// 处理前导零for (int num : result) {if (!(sb.length() == 0 && num == 0)) {sb.append(num);}}return sb.toString();}

寻找两个正序数组的中位数（LeetCode 4）

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {if (nums1.length > nums2.length) {int[] temp = nums1;nums1 = nums2;nums2 = temp;}int m = nums1.length;int n = nums2.length;int imin = 0, imax = m, halfLen = (m + n + 1) / 2;while (imin <= imax) {int i = (imin + imax) / 2;int j = halfLen - i;if (i < m && nums2[j - 1] > nums1[i]) {// i 太小，需要增大imin = i + 1;} else if (i > 0 && nums1[i - 1] > nums2[j]) {// i 太大，需要减小imax = i - 1;} else {// i 是完美的分割点int maxOfLeft;if (i == 0) {maxOfLeft = nums2[j - 1];} else if (j == 0) {maxOfLeft = nums1[i - 1];} else {maxOfLeft = Math.max(nums1[i - 1], nums2[j - 1]);}if ((m + n) % 2 == 1) {return maxOfLeft;}int minOfRight;if (i == m) {minOfRight = nums2[j];} else if (j == n) {minOfRight = nums1[i];} else {minOfRight = Math.min(nums1[i], nums2[j]);}return (maxOfLeft + minOfRight) / 2.0;}}return 0.0;}

整数反转（LeetCode 7）

    public int reverse(int x) {int sign = x < 0 ? -1 : 1;x = Math.abs(x);int result = 0;while (x != 0) {int digit = x % 10;x /= 10;// 检查是否溢出if (result > (Integer.MAX_VALUE - digit) / 10) {return 0;}result = result * 10 + digit;}result *= sign;return result;}

最大公约数（LeetCode 1071）

    public String gcdOfStrings(String str1, String str2) {int gcdLength = gcd(str1.length(), str2.length());for (int length = gcdLength; length > 0; length--) {if (gcdLength % length == 0) {String candidate = str1.substring(0, length);if (repeatString(candidate, str1.length() / length).equals(str1) && repeatString(candidate, str2.length() / length).equals(str2)) {return candidate;}}}return "";}// 求最大公约数private int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}// 重复字符串private String repeatString(String s, int n) {StringBuilder sb = new StringBuilder();for (int i = 0; i < n; i++) {sb.append(s);}return sb.toString();}

二分查找

第一个错误的版本（LeetCode 278）

    public int firstBadVersion(int n) {int left = 1;  // 定义左边界为 1int right = n;  // 定义右边界为 nwhile (left < right) {  // 当左边界小于右边界时，进行二分查找int mid = left + (right - left) / 2;  // 计算中间位置if (isBadVersion(mid)) {  // 如果中间位置是坏版本right = mid;  // 将右边界更新为中间位置} else {  // 如果中间位置不是坏版本left = mid + 1;  // 将左边界更新为中间位置的下一个}}return left;  // 返回最终的左边界，即为第一个坏版本}

搜索插入位置（LeetCode 35）

    public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length - 1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] == target) {return mid;} else if(nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;}

寻找峰值（LeetCode 162）

    public int findPeakElement(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[mid + 1]) {right = mid;} else {left = mid + 1;}}return left;}

寻找两个正序数组的中位数（LeetCode 4）

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m = nums1.length;int n = nums2.length;int left = (m + n + 1) / 2;int right = (m + n + 2) / 2;return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;}private int findKth(int[] nums1, int i, int[] nums2, int j, int k) {if (i >= nums1.length) return nums2[j + k - 1];if (j >= nums2.length) return nums1[i + k - 1];if (k == 1) return Math.min(nums1[i], nums2[j]);int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;if (midVal1 < midVal2) {return findKth(nums1, i + k / 2, nums2, j, k - k / 2);} else {return findKth(nums1, i, nums2, j + k / 2, k - k / 2);}}

数组

移动零（LeetCode 283）

    public void moveZeroes(int[] nums) {int j = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {nums[j] = nums[i];++j;}}for (int i = j; i < nums.length; i++) {nums[i] = 0;}}

颜色分类（LeetCode 75）

        int left = 0, right = nums.length - 1, current = 0;while (current <= right) {if (nums[current] == 0) {swap(nums, left, current);left++;current++;} else if (nums[current] == 2) {swap(nums, right, current);right--;} else {current++;}}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}

旋转有序数组中的搜索（LeetCode 33）

    public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;}if (nums[left] <= nums[mid]) {if (nums[left] <= target && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else {if (nums[mid] < target && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}   return -1;}

合并两个有序数组（LeetCode 88）

    public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m - 1, j = n - 1, k = m + n - 1;while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) {nums1[k] = nums1[i];i--;} else {nums1[k] = nums2[j];j--;}k--;}while (j >= 0) {nums1[k] = nums2[j];j--;k--;}}

链表

链表的中间节点（LeetCode 876）

    public ListNode middleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}

排序链表（LeetCode 148）

    public ListNode sortList(ListNode head) {return sort(head, null);}private ListNode sort(ListNode head, ListNode tail) {if (head == null) return head;if (head.next == tail) {head.next = null;return head;}ListNode slow = head, fast = head;while (fast != tail) {slow = slow.next;fast = fast.next;if (fast != tail) fast = fast.next;}ListNode l1 = sort(head, slow);ListNode l2 = sort(slow, tail);return merge(l1, l2);}private ListNode merge(ListNode n1, ListNode n2) {ListNode dummy = new ListNode();ListNode cur = dummy;while (n1 != null && n2 != null) {if (n1.val <= n2.val) {cur.next = n1;n1 = n1.next;} else {cur.next = n2;n2 = n2.next;}cur = cur.next;}cur.next = n1 != null ? n1 : n2;return dummy.next;}

重排链表（LeetCode 143）

    public void reorderList(ListNode head) {if (head == null) return;// 找到中间转折的点ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}System.out.println("slow -> " + slow.val);// 翻转后边的列表ListNode nl = new ListNode();while (slow.next != null) {ListNode tmp = slow.next;// 移除主链表slow.next = slow.next.next;// 放入翻转链表tmp.next = nl.next;nl.next = tmp;}// 合并链表ListNode cur = head;while (nl.next != null) {ListNode tmp = nl.next;nl.next = nl.next.next;// 加入主链表tmp.next = cur.next;cur.next = tmp;cur = cur.next.next;System.out.print(".");}}

反转链表（LeetCode 206）

  public ListNode reverseList(ListNode head) {ListNode prev = null, curr = head;while (curr != null) {ListNode nextTemp = curr.next;curr.next = prev;prev = curr;curr = nextTemp;}   return prev;}

两两交换链表中的节点（LeetCode 24）

    public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode prev = dummy;while (head != null && head.next != null) {ListNode first = head;ListNode second = head.next;prev.next = second;first.next = second.next;second.next = first;prev = first;head = first.next;}return dummy.next;}

合并 K 个升序链表（LeetCode 23）

    public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) {return null;}ListNode result = lists[0];for (int i = 1; i < lists.length; i++) {result = mergeTwoLists(result, lists[i]);}return result;}// 合并两个有序链表的方法private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode current = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}if (l1 != null) {current.next = l1;}if (l2 != null) {current.next = l2;}return dummy.next;}

环形链表（LeetCode 141）

    public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head.next;while (slow != fast) {if (fast == null || fast.next == null) {return false;}slow = slow.next;fast = fast.next.next;}return true;}

环形链表 II（LeetCode 142）

    public ListNode detectCycle(ListNode head) {Set<ListNode> set = new HashSet<>();ListNode cur = head;while (cur != null) {if (!set.add(cur)) {return cur;}cur = cur.next;}return null;}

删除排序链表中的重复元素（LeetCode 83）

    public ListNode deleteDuplicates(ListNode head) {ListNode cur = head;while (cur != null && cur.next != null) {if (cur.val == cur.next.val) {cur.next = cur.next.next;} else {cur = cur.next;}}return head;}

删除排序链表中的重复元素 II（LeetCode 82）

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy;ListNode cur = head;while (cur != null) {boolean hasD = false;while (cur.next != null && cur.val == cur.next.val) {hasD = true;cur = cur.next;}if (hasD) {pre.next = cur.next;} else {pre = pre.next;}cur = cur.next;}return dummy.next;}

回文链表（LeetCode 234）

    public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 找到链表中间节点ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}// 反转后半部分链表ListNode secondHalf = reverseList(slow.next);ListNode firstHalf = head;// 比较两部分链表while (secondHalf != null) {if (firstHalf.val != secondHalf.val) {return false;}firstHalf = firstHalf.next;secondHalf = secondHalf.next;}return true;}private ListNode reverseList(ListNode head) {ListNode prev = null;ListNode current = head;while (current != null) {ListNode nextNode = current.next;current.next = prev;prev = current;current = nextNode;}return prev;}

相交链表（LeetCode 160）

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pA = headA;ListNode pB = headB;while (pA != pB) {pA = pA != null ? pA.next : headB;pB = pB != null ? pB.next : headA;}return pA;}

奇偶链表（LeetCode 328）

    public ListNode oddEvenList(ListNode head) {if (head == null || head.next == null) {return head;}// 奇数链表的头节点ListNode odd = head;// 偶数链表的头节点ListNode even = head.next;// 保存偶数链表的头节点，用于后续连接ListNode evenHead = even;while (even != null && even.next != null) {// 连接奇数节点odd.next = even.next;odd = odd.next;// 连接偶数节点even.next = odd.next;even = even.next;}// 将偶数链表连接到奇数链表的末尾odd.next = evenHead;return head;}

删除链表元素（LeetCode 203）

    public ListNode removeElements(ListNode head, int val) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode current = dummy;while (current.next != null) {if (current.next.val == val) {current.next = current.next.next;} else {current = current.next;}}return dummy.next;}

单链表的倒数第 K 个节点（LeetCode 19）

    public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode first = dummy;ListNode second = dummy;// 让 first 指针先移动 n + 1 步for (int i = 0; i <= n; i++) {first = first.next;}// 同时移动 first 和 second 指针while (first != null) {first = first.next;second = second.next;}// 删除倒数第 n 个节点second.next = second.next.next;return dummy.next;}

栈

有效的括号（LeetCode 20）

    public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c: s.toCharArray()) {if (c == '(' || c == '[' || c == '{') {stack.push(c);} else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {stack.pop();} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {stack.pop();} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {stack.pop();} else {return false;}}return stack.isEmpty();}

最小栈（LeetCode 155）

    public int trap(int[] height) {if (height == null || height.length == 0) {return 0;}int left = 0, right = height.length - 1;int leftMax = 0, rightMax = 0;int result = 0;while (left < right) {if (height[left] < height[right]) {if (height[left] >= leftMax) {leftMax = height[left];} else {result += leftMax - height[left];}left++;} else {if (height[right] >= rightMax) {rightMax = height[right];} else {result += rightMax - height[right];}right--;}}return result;}

接雨水（LeetCode 42）

    public int largestRectangleArea(int[] heights) {if (heights == null || heights.length == 0) {return 0;}int n = heights.length;int[] left = new int[n];int[] right = new int[n];Stack<Integer> stack = new Stack<>();for (int i = 0; i < n; i++) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}left[i] = stack.isEmpty() ? -1 : stack.peek();stack.push(i);}stack.clear();for (int i = n - 1; i >= 0; i--) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}right[i] = stack.isEmpty() ? n : stack.peek();stack.push(i);}int maxArea = 0;for (int i = 0; i < n; i++) {maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));}return maxArea;}

直方图中的最大矩形（LeetCode 84）

    public int largestRectangleArea(int[] heights) {if (heights == null || heights.length == 0) {return 0;}int n = heights.length;int[] left = new int[n];int[] right = new int[n];Stack<Integer> stack = new Stack<>();for (int i = 0; i < n; i++) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}left[i] = stack.isEmpty() ? -1 : stack.peek();stack.push(i);}stack.clear();for (int i = n - 1; i >= 0; i--) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}right[i] = stack.isEmpty() ? n : stack.peek();stack.push(i);}int maxArea = 0;for (int i = 0; i < n; i++) {maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));}return maxArea;}

队列

滑动窗口最大值（LeetCode 239）

    public int[] maxSlidingWindow(int[] nums, int k) {if (nums == null || nums.length == 0) {return new int[0];}int n = nums.length;int[] result = new int[n - k + 1];Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i < n; i++) {while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {deque.pollFirst();}while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();}deque.offerLast(i);if (i >= k - 1) {result[i - k + 1] = nums[deque.peekFirst()];}}return result;}

最小窗口子串（LeetCode 76）

    public String minWindow(String s, String t) {if (s == null || s.length() == 0 || t == null || t.length() == 0) {return "";}int[] need = new int[128];for (char c : t.toCharArray()) {need[c]++;}int left = 0, right = 0, start = 0, minLen = Integer.MAX_VALUE, count = t.length();while (right < s.length()) {char c = s.charAt(right);if (need[c] > 0) {count--;}need[c]--;right++;while (count == 0) {if (right - left < minLen) {minLen = right - left;start = left;}char leftChar = s.charAt(left);need[leftChar]++;if (need[leftChar] > 0) {count++;}left++;}}return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);}

设计循环双端队列（LeetCode 641）

    private int[] data;private int front;private int rear;private int size;public MyCircularDeque(int k) {data = new int[k];front = 0;rear = 0;size = 0;}public boolean insertFront(int value) {if (isFull()) {return false;}front = (front - 1 + data.length) % data.length;data[front] = value;size++;return true;}public boolean insertLast(int value) {if (isFull()) {return false;}data[rear] = value;rear = (rear + 1) % data.length;size++;return true;}public boolean deleteFront() {if (isEmpty()) {return false;}front = (front + 1) % data.length;size--;return true;}public boolean deleteLast() {if (isEmpty()) {return false;}rear = (rear - 1 + data.length) % data.length;size--;return true;}public int getFront() {if (isEmpty()) {return -1;}return data[front];}public int getRear() {if (isEmpty()) {return -1;}return data[(rear - 1 + data.length) % data.length];}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == data.length;}

双指针

两数之和（LeetCode 167）

    public int[] twoSum(int[] numbers, int target) {int left = 0;int right = numbers.length - 1;while (left < right) {int sum = numbers[left] + numbers[right];if (sum == target) {return new int[]{left + 1, right + 1};} else if (sum < target) {left++;} else {right--;}}// This line should never be reached since there is exactly one solutionreturn new int[]{-1, -1};}
}

三数之和（LeetCode 15）

    public List<List<Integer>> threeSum(int[] nums) {// Initialize the result list to store the tripletsList<List<Integer>> result = new ArrayList<>();// Sort the array in ascending order to simplify the process of finding tripletsArrays.sort(nums);// Iterate through the array, considering each element as a potential first element of a tripletfor (int i = 0; i < nums.length - 2; i++) {// Skip duplicates for the first number to avoid duplicate tripletsif (i > 0 && nums[i] == nums[i - 1]) continue;// Initialize two pointers, one at the next element and one at the end of the arrayint left = i + 1;int right = nums.length - 1;// Calculate the target sum for the other two numbersint target = -nums[i];// Use two-pointer approach to find the other two numbers that sum up to the targetwhile (left < right) {// Calculate the sum of the two numbers pointed by the left and right pointersint sum = nums[left] + nums[right];// If the sum is equal to the target, we found a tripletif (sum == target) {// Add the triplet to the result listresult.add(Arrays.asList(nums[i], nums[left], nums[right]));// Skip duplicates for the second and third numberswhile (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;// Move the pointers to the next unique numbersleft++;right--;}// If the sum is less than the target, move the left pointer to the right to increase the sumelse if (sum < target) {left++;}// If the sum is greater than the target, move the right pointer to the left to decrease the sumelse {right--;}}}// Return the list of tripletsreturn result;}

四数之和（LeetCode 18）

    public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums); // Sort the array firstfor (int i = 0; i < nums.length - 3; i++) {// Skip duplicates for the first numberif (i > 0 && nums[i] == nums[i - 1]) continue;for (int j = i + 1; j < nums.length - 2; j++) {// Skip duplicates for the second numberif (j > i + 1 && nums[j] == nums[j - 1]) continue;int left = j + 1;int right = nums.length - 1;long newTarget = (long) target - nums[i] - nums[j];while (left < right) {long sum = (long) nums[left] + nums[right];if (sum == newTarget) {result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));// Skip duplicates for the third and fourth numberswhile (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;left++;right--;} else if (sum < newTarget) {left++;} else {right--;}}}}return result;}

移除元素（LeetCode 27）

    public int removeElement(int[] nums, int val) {int k = 0; // Initialize the pointer for the next position to place a non-val elementfor (int i = 0; i < nums.length; i++) {if (nums[i] != val) {nums[k] = nums[i]; // Place the non-val element at the next positionk++; // Move the pointer to the next position}}return k; // Return the number of elements that are not equal to val}

反转字符串（LeetCode 344）

    public boolean isPalindrome(String s) {// Convert the string to lowercase and remove non-alphanumeric charactersString cleanString = s.toLowerCase().replaceAll("[^a-z0-9]", "");// Check if the clean string is a palindromeint left = 0;int right = cleanString.length() - 1;while (left < right) {if (cleanString.charAt(left) != cleanString.charAt(right)) {return false;}left++;right--;}return true;}

验证回文串（LeetCode 125）

    public boolean isPalindrome(String s) {String cleanStr = s.toLowerCase().replaceAll("[^a-z0-9]", "");int left = 0;int right = cleanStr.length() - 1;while(left < right) {if(cleanStr.charAt(left) != cleanStr.charAt(right)) {return false;}left++;right--;}return true;}

哈希表

两数之和（LeetCode 1）

    public int[] twoSum(int[] nums, int target) {if (nums == null || nums.length == 0) {return new int[0];}Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int com = target - nums[i];if (map.containsKey(com)) {return new int[]{map.get(com), i};}map.put(nums[i], i);}return new int[0];}

字母异位词分组（LeetCode 49）

    public List<List<String>> groupAnagrams(String[] strs) {if (strs == null || strs.length == 0) {return new ArrayList<>();}Map<String, List<String>> map = new HashMap<>();for (String str : strs) {char[] charArray = str.toCharArray();Arrays.sort(charArray);String sortedStr = new String(charArray);if (!map.containsKey(sortedStr)) {map.put(sortedStr, new ArrayList<>());}map.get(sortedStr).add(str);}return new ArrayList<>(map.values());}

四数相加 II（LeetCode 454）

    public List<List<String>> groupAnagrams(String[] strs) {if (strs == null || strs.length == 0) {return new ArrayList<>();}Map<String, List<String>> map = new HashMap<>();for (String str : strs) {char[] charArray = str.toCharArray();Arrays.sort(charArray);String sortedStr = new String(charArray);if (!map.containsKey(sortedStr)) {map.put(sortedStr, new ArrayList<>());}map.get(sortedStr).add(str);}return new ArrayList<>(map.values());}

快乐数（LeetCode 202）

    public boolean isHappy(int n) {Set<Integer> set = new HashSet<>();while (n != 1 && !set.contains(n)) {set.add(n);n = getNext(n);}return n == 1;}private int getNext(int n) {int total = 0;while(n > 0) {int digit = n % 10;total += digit * digit;n = n / 10;}return total;}

赎金信（LeetCode 383）

    public boolean canConstruct(String ransomNote, String magazine) {int[] count = new int[26];for (char c : magazine.toCharArray()) {count[c - 'a']++;}for (char c : ransomNote.toCharArray()) {if (--count[c - 'a'] < 0) {return false;}}return true;}

第一个只出现一次的字符（LeetCode 387）

    public int firstUniqChar(String s) {Map<Character, Integer> map = new HashMap<>();char[] charArray = s.toCharArray();for (char c : charArray) {map.put(c, map.getOrDefault(c, 0) + 1);}for (int i = 0; i < charArray.length; i++) {if (map.get(charArray[i]) == 1) {return i;}}return -1;}

存在重复元素（LeetCode 217）

    public boolean containsDuplicate(int[] nums) {Set<Integer> set = new HashSet<>();for (int num : nums) {if (!set.add(num)) {return true;}}return false;}

存在重复元素 II（LeetCode 219）

    public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int num = nums[i];if (map.containsKey(num) && i - map.get(num) <= k) {return true;}map.put(num, i);}return false;}

两个数组的交集（LeetCode 349）

    public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();for (int num : nums1) {set1.add(num);}Set<Integer> set2 = new HashSet<>();for (int num : nums2) {if (set1.contains(num)) {set2.add(num;)}}int[] result = new int[set2.size()];int index = 0;for (int num : set2) {result[i++] = num;}return result;}

两个数组的交集 II（LeetCode 350）

    public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();for (int num : nums1) {set1.add(num);}Set<Integer> set2 = new HashSet<>();for (int num : nums2) {if (set1.contains(num)) {set2.add(num);}}int[] result = new int[set2.size()];int index = 0;for (int num : set2) {result[index++] = num;}return result;}

前缀和

最大子序和（LeetCode 53）

    public int maxSubArray(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] prefixSum = new int[n + 1];prefixSum[0] = 0;for (int i = 1; i <= n; i++) {prefixSum[i] = prefixSum[i - 1] + nums[i - 1];}int minPrefixSum = 0;int maxSubArraySum = Integer.MIN_VALUE;for (int i = 1; i <= n; i++) {maxSubArraySum = Math.max(maxSubArraySum, prefixSum[i] - minPrefixSum);minPrefixSum = Math.min(minPrefixSum, prefixSum[i]);}return maxSubArraySum;}

和为 K 的子数组（LeetCode 560）

    public int subarraySum(int[] nums, int k) {if (nums == null || nums.length == 0) {return 0;}int count = 0;int prefixNum = 0;Map<Integer, Integer> map = new HashMap<>();map.put(0, 1);for (int num: nums) {prefixNum += num;if (map.containsKey(prefixNum - k)) {count += map.get(prefixNum - k);}map.put(prefixNum, map.getOrDefault(prefixNum, 0) + 1);}return count;}

寻找数组的中心下标（LeetCode 724）

    public int pivotIndex(int[] nums) {if (nums == null || nums.length == 0) {return -1;}int total = 0;for (int num: nums) {total += num;}int left = 0;for (int i = 0; i < nums.length; i++) {if (left == total - left - nums[i]) {return i;}left += nums[i];}return -1;}

长度最小的子数组（LeetCode 209）

    public int minSubArrayLen(int target, int[] nums) {if (nums == null || nums.length == 0) {return 0;}int min = Integer.MAX_VALUE;int left = 0;int sum = 0;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= target) {min = Math.min(min, right - left + 1);sum -= nums[left];left++;}}return min == Integer.MAX_VALUE ? 0 : min;}

二叉树

二叉树的前序遍历（LeetCode 144）

    public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorder(root, result);return result;}private void preorder(TreeNode node, List<Integer> result) {if (node == null) {return;}result.add(node.val);preorder(node.left, result);preorder(node.right, result);}

二叉树的中序遍历（LeetCode 94）

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorder(root, result);return result;}private void inorder(TreeNode node, List<Integer> result) {if (node == null) {return;}inorder(node.left, result);result.add(node.val);inorder(node.right, result);}

二叉树的后序遍历（LeetCode 145）

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorder(root, result);return result;}private void inorder(TreeNode node, List<Integer> result) {if (node == null) {return;}inorder(node.left, result);inorder(node.right, result);result.add(node.val);}

最大二叉树（LeetCode 654）

    public TreeNode constructMaximumBinaryTree(int[] nums) {return build(nums, 0, nums.length - 1);}private TreeNode build(int[] nums, int left, int right) {if (left > right) {return null;}int maxIndex = left;for (int i = left + 1; i <= right; i++) {if (nums[i] > nums[maxIndex]) {maxIndex = i;}}TreeNode root = new TreeNode(nums[maxIndex]);root.left = build(nums, left, maxIndex - 1);root.right = build(nums, maxIndex + 1, right);return root;}

二叉树的层序遍历（LeetCode 102）

    public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int levelSize = queue.size();List<Integer> currentLevel = new ArrayList<>();for (int i = 0; i < levelSize; i++) {TreeNode node = queue.pollFirst();currentLevel.add(node.val);if (node.left != null) {queue.offerLast(node.left);}if (node.right != null) {queue.offerLast(node.right);}}result.add(currentLevel);}return result;}

二叉树的最小深度（LeetCode 111）

    public int minDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}int minDepth = Integer.MAX_VALUE;if (root.left != null) {minDepth = Math.min(minDepth, minDepth(root.left));}if (root.right != null) {minDepth = Math.min(minDepth, minDepth(root.right));}return minDepth + 1;}

二叉树的最大深度（LeetCode 104）

    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;}

二叉树的最近公共祖先（LeetCode 236）

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left != null && right != null) {return root;} else if (left != null) {return left;} else {return right;}}

对称二叉树（LeetCode 101）

    public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isMirror(root.left, root.right);}private boolean isMirror(TreeNode left, TreeNode right) {if (left == null && right == null) {return true;}if (left == null || right == null) {return false;}return (left.val == right.val) && isMirror(left.left, right.right) && isMirror(left.left, right.left);}

翻转二叉树（LeetCode 226）

    public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode temp = root.left;root.left = root.right;root.right = temp;invertTree(root.left);invertTree(root.right);return root;}

从中序与后序遍历序列构造二叉树

    public TreeNode buildTree(int[] inorder, int[] postorder) {return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);}private TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {if (inStart > inEnd || postStart > postEnd) {return null;}int rootVal = postorder[postEnd];TreeNode root = new TreeNode(rootVal);int rootIndexInorder = 0;for (int i = inStart; i <= inEnd; i++) {if (inorder[i] == rootVal) {rootIndexInorder = i;break;}}int leftSubtreeSize = rootIndexInorder - inStart;root.left = build(inorder, inStart, rootIndexInorder - 1, postorder, postStart, postStart + leftSubtreeSize - 1);root.right = build(inorder, rootIndexInorder + 1, inEnd, postorder, postStart + leftSubtreeSize, postEnd - 1);return root;}

从前序与中序遍历序列构造二叉树（LeetCode 105）

    public TreeNode buildTree(int[] preorder, int[] inorder) {return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);}private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {if (preStart > preEnd || inStart > inEnd) {return null;}int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);int rootIndexInorder = 0;for (int i = inStart; i <= inEnd; i++) {if (inorder[i] == rootVal) {rootIndexInorder = i;break;}}int leftSubtreeSize = rootIndexInorder - inStart;root.left = build(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, rootIndexInorder - 1);root.right = build(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, rootIndexInorder + 1, inEnd);return root;}