跳到主要内容

分治 (Divide and Conquer)

分治算法将大规模问题分解为独立子问题，解决子问题后进行合并。

108. 将有序数组转换为二叉搜索树 (Convert Sorted Array to Binary Search Tree)​

题目描述​

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

解题思路​

二分递归构建。

  1. 选择数组中间元素作为根节点 mid = (L + R) / 2。
  2. 递归左半部构建左子树：node.left = build(nums, L, mid - 1)。
  3. 递归右半部构建右子树：node.right = build(nums, mid + 1, R)。

Java 代码实现​

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    private TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int mid = (l + r) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = build(nums, l, mid - 1);
        node.right = build(nums, mid + 1, r);
        return node;
    }
}

148. 排序链表 (Sort List)​

题目描述​

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

解题思路​

归并排序 + 快慢指针中点。

  1. 使用快慢指针找到链表中点。
  2. 递归对左右两半部分进行排序。
  3. 将两个有序链表合并（同 21 题）。

Java 代码实现​

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        return merge(sortList(head), sortList(mid));
    }
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) { curr.next = l1; l1 = l1.next; }
            else { curr.next = l2; l2 = l2.next; }
            curr = curr.next;
        }
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

23. 合并 K 个升序链表 (Merge k Sorted Lists)​

题目描述​

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

解题思路​

分治合并 (Divide and Conquer Merge)。

  1. 将 kk 个链表分成两组，各自合并后，再对两组结果进行最终合并。
  2. 递归深度为 log⁡k\log k，总时间复杂度 O(Nlog⁡k)O(N \log k)。
  3. 也可以借助最小堆实现。

Java 代码实现​

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }
    private ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) return lists[l];
        int mid = (l + r) / 2;
        return mergeTwo(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    private ListNode mergeTwo(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) { curr.next = l1; l1 = l1.next; }
            else { curr.next = l2; l2 = l2.next; }
            curr = curr.next;
        }
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

427. 建立四叉树 (Construct Quad Tree)​

题目描述​

给你一个 n x n 矩阵 grid ，矩阵由 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

四叉树 是一种树形数据结构，其每个内节点都有四个子节点：topLeft、topRight、bottomLeft 和 bottomRight 。当一个区域内的所有网格具有相同值时，四叉树将该区域表示为叶节点。

解题思路​

区域全等判定 + 递归分解。

  1. 定义递归函数 construct(r, c, len)。
  2. 基础步骤：遍历 (r, c) 到 (r+len, c+len) 的区域。
  3. 如果区域内所有值相等：
    • 当前节点为叶子节点 (isLeaf = true)。
    • 值为该区域的值。
    • 子节点全部为 null。
  4. 如果区域内值不相等：
    • 当前节点不是叶子节点 (isLeaf = false)。
    • 值可以是任意值（通常为 1）。
    • 递归构建四个子区域（左上、右上、左下、右下），每个子区域边的长度为 len / 2。

Java 代码实现​

class Solution {
    public Node construct(int[][] grid) {
        return build(grid, 0, 0, grid.length);
    }
    private Node build(int[][] grid, int r, int c, int len) {
        boolean same = true;
        for (int i = r; i < r + len; i++) {
            for (int j = c; j < c + len; j++) {
                if (grid[i][j] != grid[r][c]) {
                    same = false;
                    break;
                }
            }
        }
        if (same) return new Node(grid[r][c] == 1, true);
        Node node = new Node(true, false);
        int half = len / 2;
        node.topLeft = build(grid, r, c, half);
        node.topRight = build(grid, r, c + half, half);
        node.bottomLeft = build(grid, r + half, c, half);
        node.bottomRight = build(grid, r + half, c + half, half);
        return node;
    }
}