🔥 常见高频算法题 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）
   • 剪枝优化要说明