《常见高频算法题 Java 解法实战精讲（3）：排序与二叉树》

🔥 常见高频算法题 Java 解法实战精讲（3）：排序与二叉树

🧠前言

在 Java 后端面试中，排序和二叉树题型几乎是必考题。

• 排序算法体现你对数据结构与时间复杂度的理解。

• 二叉树题目考察递归、迭代、回溯、队列等综合能力。

我们这篇文章聚焦两个部分：

1.排序（快速排序、堆排序）

2.二叉树（遍历、路径问题）

并结合 LeetCode 高频题 做实战讲解。

一、排序算法：高效数据处理的基石

💡 排序算法对比

⚡️ 时间复杂度概览

算法	平均时间复杂度	最坏情况	空间复杂度	稳定性
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定

二、快速排序：分治的艺术

💡 分治原理图解

⚙️ Java递归实现

public void quickSort(int[] arr, int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}
}private int partition(int[] arr, int low, int high) {int pivot = arr[high]; // 选择最后一个元素为基准int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;
}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

🔄 非递归实现（栈模拟）

public void quickSortIterative(int[] arr) {Stack<Integer> stack = new Stack<>();stack.push(0);stack.push(arr.length - 1);while (!stack.isEmpty()) {int high = stack.pop();int low = stack.pop();int pivot = partition(arr, low, high);if (pivot - 1 > low) {stack.push(low);stack.push(pivot - 1);}if (pivot + 1 < high) {stack.push(pivot + 1);stack.push(high);}}
}

⚡️ 优化策略

// 三数取中法选择基准
private int selectPivot(int[] arr, int low, int high) {int mid = low + (high - low) / 2;if (arr[low] > arr[mid]) swap(arr, low, mid);if (arr[low] > arr[high]) swap(arr, low, high);if (arr[mid] > arr[high]) swap(arr, mid, high);return mid;
}// 小区间使用插入排序
if (high - low < 10) {insertionSort(arr, low, high);return;
}

三、堆排序：二叉堆的智慧

💡 堆结构原理

⚙️ 堆排序流程

🔧 Java实现

public 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--) {swap(arr, 0, i); // 移动当前最大值到末尾heapify(arr, i, 0); // 调整剩余堆}
}private 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) {swap(arr, i, largest);heapify(arr, n, largest); // 递归调整子树}
}

⚠️ 常见坑点

// 错误：数组下标从1开始计算
// 正确：数组下标从0开始
int left = 2 * i + 1; // 非2*i
int right = 2 * i + 2; // 非2*i+1// 错误：忘记递归调整子树
// 正确：交换后递归调整

四、二叉树遍历：深度与广度的探索

💡 遍历方式对比

⚙️ 递归实现

// 前序遍历
void preOrder(TreeNode root) {if (root == null) return;System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);
}// 中序遍历
void inOrder(TreeNode root) {if (root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);
}// 后序遍历
void postOrder(TreeNode root) {if (root == null) return;postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");
}

🔄 迭代实现

// 前序遍历（使用栈）
public List<Integer> preOrderIterative(TreeNode root) {List<Integer> result = new ArrayList<>();Deque<TreeNode> stack = new ArrayDeque<>();if (root != null) stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val);if (node.right != null) stack.push(node.right);if (node.left != null) stack.push(node.left);}return result;
}// 中序遍历（使用栈）
public List<Integer> inOrderIterative(TreeNode root) {List<Integer> result = new ArrayList<>();Deque<TreeNode> stack = new ArrayDeque<>();TreeNode curr = root;while (curr != null || !stack.isEmpty()) {while (curr != null) {stack.push(curr);curr = curr.left;}curr = stack.pop();result.add(curr.val);curr = curr.right;}return result;
}// 层序遍历（使用队列）
public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();List<Integer> level = new ArrayList<>();for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}result.add(level);}return result;
}

五、二叉树路径搜索：回溯的艺术

💡 回溯算法框架

void backtrack(TreeNode node, List<Integer> path, List<List<Integer>> result) {// 终止条件if (node == null) return;// 做出选择path.add(node.val);// 满足条件时记录结果if (node.left == null && node.right == null) {result.add(new ArrayList<>(path));}// 递归探索backtrack(node.left, path, result);backtrack(node.right, path, result);// 撤销选择path.remove(path.size() - 1);
}

⚙️ 路径和问题

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> result = new ArrayList<>();backtrack(root, targetSum, new ArrayList<>(), result);return result;
}private void backtrack(TreeNode node, int remain, List<Integer> path, List<List<Integer>> result) {if (node == null) return;path.add(node.val);remain -= node.val;if (node.left == null && node.right == null && remain == 0) {result.add(new ArrayList<>(path));} else {backtrack(node.left, remain, path, result);backtrack(node.right, remain, path, result);}path.remove(path.size() - 1);
}

六、LeetCode高频题精讲

💡 215. 数组第K大元素

​​题目描述​​：

在未排序数组中找到第K个最大的元素

​​快速选择解法​​：

public int findKthLargest(int[] nums, int k) {int left = 0, right = nums.length - 1;while (true) {int pivot = partition(nums, left, right);if (pivot == k - 1) return nums[pivot];if (pivot < k - 1) left = pivot + 1;else right = pivot - 1;}
}private int partition(int[] nums, int low, int high) {int pivot = nums[high];int i = low;for (int j = low; j < high; j++) {if (nums[j] >= pivot) {swap(nums, i, j);i++;}}swap(nums, i, high);return i;
}

复杂度​​：平均O(n)，最坏O(n²)

💡 94. 二叉树中序遍历

​​题目描述​​：

返回二叉树中序遍历结果

​​迭代解法​​：

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> stack = new ArrayDeque<>();TreeNode curr = root;while (curr != null || !stack.isEmpty()) {while (curr != null) {stack.push(curr);curr = curr.left;}curr = stack.pop();res.add(curr.val);curr = curr.right;}return res;
}

**复杂度​​：**O(n)时间，O(n)空间

💡 113. 二叉树路径和II

​​题目描述​​：

找出所有从根到叶路径和等于目标值的路径

​​回溯解法​​：

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> result = new ArrayList<>();backtrack(root, targetSum, new ArrayList<>(), result);return result;
}private void backtrack(TreeNode node, int remain, List<Integer> path, List<List<Integer>> result) {if (node == null) return;path.add(node.val);remain -= node.val;if (node.left == null && node.right == null && remain == 0) {result.add(new ArrayList<>(path));}backtrack(node.left, remain, path, result);backtrack(node.right, remain, path, result);path.remove(path.size() - 1);
}

复杂度​​： O(n)时间，O(n)空间

七、知识点总结表

💡 排序算法对比

算法	平均时间复杂度	最坏情况	空间复杂度	稳定性	适用场景
快速排序	O(n log n)	O(n²)	O(log n)	不稳定	通用排序
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	内存受限
归并排序	O(n log n)	O(n log n)	O(n)	稳定	外部排序

🔄 二叉树遍历对比

遍历方式	递归实现	迭代实现	应用场景
前序	简单	栈+右左	复制树结构
中序	简单	栈+左链	有序输出
后序	简单	双栈/反转	释放内存
层序	不适用	队列	层级操作

⚡️ 路径问题解法

问题类型	解法	时间复杂度	空间复杂度
单路径存在	递归DFS	O(n)	O(h)
所有路径	回溯	O(n)	O(h)
路径和	回溯+剪枝	O(n)	O(h)

八、结语

🏆 核心要点回顾

📝 面试必备技巧

1. 排序选择：

   • 面试优先展示快速排序
   • 内存受限时提到堆排序
   • 稳定需求时说明归并排序

2. 二叉树遍历：

   • 递归写法必须掌握
   • 迭代写法展示技巧
   • 层序遍历必写队列实现

3. 路径问题：

   • 回溯框架要熟练
   • 注意路径复制（new ArrayList）
   • 剪枝优化要说明