难度说明：🟢简单🟡中等🔴困难

hot150-13-分治

🟢01-将有序数组转换为二叉搜索树（108）

1.题目内容

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

2.题解思路

👻方法1：中点拆分

• 思路分析：直接将中点作为根节点，然后中点左侧作为左子树，中点右侧作为右子树，如果传入nums为空说明是空节点不需要进行构建（返回null）
  • 但需注意如果nums过大时，可能需要额外的数组复制开销

/**
 * 108 将有序数组转化为二叉搜索树
 * 平衡二叉搜索树的特点，其中序遍历结果是连续升序序列
 */
public class Solution1 {
    // 数组本身有序，将中点作为根节点，中点左侧的作为左子树、中点右侧的作为右子树
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums);
    }

    public TreeNode build(int[] nums) {
        // 如果传入的nums为空或者长度为0则不需要构建
        if (nums == null || nums.length == 0) {
            return null;
        }

        // 计算中点索引位置
        int mid = nums.length / 2;

        // 创建根节点
        TreeNode root = new TreeNode(nums[mid]);
        // 分别构建左右节点
        root.left = build(Arrays.copyOfRange(nums, 0, mid));
        root.right = build(Arrays.copyOfRange(nums, mid + 1, nums.length));

        // 返回构建的节点
        return root;
    }

}

• 复杂度分析

  • 时间复杂度：O（n）n为数组长度

  • 空间复杂度：

👻方法2：中序遍历，总是选择中间位置左边的数字作为根节点

• 思路分析：和方法1中的思路类似，也是通过二分概念选定中点，然后根据中点拆分两侧进行递归构建。但是此处构建是通过限定数组区间的方式来避免每次都额外copy数组的开销
  • 每次选择中间位置作为根节点，使用左右索引维护数组

/**
 * 108 将有序数组转化为二叉搜索树
 * 平衡二叉搜索树的特点，其中序遍历结果是连续升序序列
 */
public class Solution2 {
    // 数组本身有序，将中点作为根节点，中点左侧的作为左子树、中点右侧的作为右子树
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    public TreeNode build(int[] nums, int left, int right) {
        // 递归出口
        if (left > right) {
            return null;
        }

        // 计算中点索引位置
        int mid = (left + right) / 2;

        // 创建根节点
        TreeNode root = new TreeNode(nums[mid]);
        // 分别构建左右节点
        root.left = build(nums, left, mid - 1);
        root.right = build(nums, mid + 1, right);

        // 返回构建的节点
        return root;
    }
}

• 复杂度分析

  • 时间复杂度：O（n）n为数组长度

  • 空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(logn)

🟡02-排序链表（148）

1.题目内容

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

2.题解思路

👻方法1：自顶向下的归并排序

• 思路分析：找中点、左右排序、合并排序结果
  • 将链表对半分（快慢指针找中点），然后分别对两边进行排序（拆开左右两部分，递归），并对排序后的结果进行合并（合并排序后的两个有序链表（左、右））

/**
 * 148 归并排序
 */
public class Solution1 {

    // 思路：归并排序（寻找链表中点，然后分别对中点左右两侧的链表进行排序，再将排序后的结果进行合并）
    public ListNode sortList(ListNode head) {
        return sortHeller(head);
    }


    public ListNode sortHeller(ListNode node) {
        // 递归出口
        if (node == null || node.next == null) {
            return node;
        }

        // 查找链表中点
        ListNode midNode = findMid(node);

        // 对右侧链表进行排序
        ListNode right = sortHeller(midNode.next);

        // 对左侧链表进行排序（断掉midNode的next即可，为了避免对右侧链表产生影响，此处需要先对右侧进行排序，或者先记录）
        midNode.next = null;
        ListNode left = sortHeller(node);

        // 返回排序后的合并结果(合并两个有序链表)
        return mergeLink(left, right);
    }


    // 查找链表中点：快慢指针思路
    public ListNode findMid(ListNode node) {
        ListNode slow = node;
        ListNode fast = node.next; // 正常思路快慢指针起点要相同，此处如果设定起点相同会出现StackOverFlow
        while (fast != null && fast.next != null) {
            slow = slow.next; // 走1步
            fast = fast.next.next; // 走2步
        }
        return slow;
    }

    // 合并两个有序链表
    public ListNode mergeLink(ListNode link1, ListNode link2) {
        // 定义虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy; // cur指针指向dummy

        // 定义指针分别用于遍历link1，link2
        ListNode point1 = link1;
        ListNode point2 = link2;

        while (point1 != null && point2 != null) {
            // 判断哪个链表指向的值比较小，则优先加入
            int val1 = point1.val;
            int val2 = point2.val;
            if (val1 <= val2) {
                // 加入新节点
                cur.next = new ListNode(val1);
                // 指针移动
                cur = cur.next;
                point1 = point1.next;
            } else {
                // 加入新节点
                cur.next = new ListNode(val2);
                // 指针移动
                cur = cur.next;
                point2 = point2.next;
            }
        }

        // 拼接剩余的链表
        if (point1 != null) {
            cur.next = point1;
        }
        if (point2 != null) {
            cur.next = point2;
        }

        // 返回合并后的结果
        return dummy.next;
    }
}

• 复杂度分析

  • 时间复杂度：O（log n）

  • 空间复杂度：O（log n）（空间复杂度取决于递归调用的栈空间）

👻方法2：遍历+排序+覆盖原链表（构建新链表）

• 思路分析：遍历 + 排序 + 构建新链表
  • 遍历一遍链表，然后放入数组或集合中进行排序，将排序后的结果构建成新链表或者是覆盖到原来的链表中

/**
 * 148 排序链表
 */
public class Solution2 {

    // 思路：遍历+排序+覆盖（构建）
    public ListNode sortList(ListNode head) {

        // 构建集合存储链表元素
        List<Integer> list= new ArrayList<>();
        ListNode cur = head;
        while(cur!=null){
            list.add(cur.val);
            cur = cur.next;
        }

        // 对集合元素进行排序
        Collections.sort(list);

        // 构建链表
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        for(int val : list){
            p.next = new ListNode(val);
            p = p.next;
        }

        // 返回构建结果
        return dummy.next;
    }

}

• 复杂度分析

  • 时间复杂度：O（n） n 链表节点个数 还需对集合元素进行排序

  • 空间复杂度：O（n）需要额外的存储空间存储链表元素

🟡03-建立四叉树（427）

1.题目内容

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

你需要返回能表示矩阵 grid 的 四叉树 的根结点。

四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：

• val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
• isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

我们可以按以下步骤为二维区域构建四叉树：

1. 如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
2. 如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
3. 使用适当的子网格递归每个子节点

2.题解思路

👻方法1：暴力递归

• 思路分析

​ 矩阵代表四叉树，正方形区域的值全相同的时候，那么这个区域代表一个叶节点，否则不是叶节点，它的叶节点就是四分对应矩阵区域所代表的的子树

/**
 * 427 建立四叉树
 */
public class Solution1 {

    public Node construct(int[][] grid) {
        return build(grid, 0, grid.length - 1, 0, grid[0].length - 1);
    }

    public Node build(int[][] grid, int rowStart, int rowEnd, int colStart, int colEnd) {
        // 如果当前矩阵元素均相同，则构建节点（表示一个叶子节点）
        if (allSame(grid, rowStart, rowEnd, colStart, colEnd)) {
            return new Node(grid[rowStart][colStart] == 1 ? true : false, true); // 设置val(1为true 0为false)、 isLeaf(全区域值相同表示为叶子节点)
        }

        // 非叶子节点的处理，需要进一步递归拆分
        int rowMid = (rowStart + rowEnd) / 2;
        int colMid = (colStart + colEnd) / 2;

        // 构建节点(闭区间写法)
        Node topLeft = build(grid, rowStart, rowMid, colStart, colMid);// 上左
        Node topRight = build(grid, rowStart, rowMid, colMid + 1, colEnd); // 上右
        Node bottomLeft = build(grid, rowMid + 1, rowEnd, colStart, colMid); // 下左
        Node bottomRight = build(grid, rowMid + 1, rowEnd, colMid + 1, colEnd); // 下右

        // 返回构建好的节点
        return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
    }

    /**
     * 判断指定区域的值是否完全相同
     * row: 从上到下
     * col：从左到右
     */
    public boolean allSame(int[][] grid, int rowStart, int rowEnd, int colStart, int colEnd) {
        //判断矩阵某区域是否同值
        for (int i = rowStart; i <= rowEnd; i++) {
            for (int j = colStart; j <= colEnd; j++) {
                if (grid[i][j] != grid[rowStart][colStart]) { // 判断每个元素是否和矩阵第一个元素相同
                    return false;
                }
            }
        }
        return true;
    }

}


/**
 * 四叉树节点定义
 */
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;


    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

🔴04-合并K个升序链表（23）

1.题目内容

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

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

2.题解思路

👻方法1：两两合并+辅助队列

• 思路分析：两两合并+辅助队列
  • （1）构建两两合并的方法（回归合并两个有序链表）
  • （2）构建辅助队列（LinkedList）存储所有链表，然后遍历队列进行两两合并（注意边界处理）

/**
 * 023 合并K个有序链表
 */
public class Solution1 {

    // 思路：两两合并+辅助队列
    public ListNode mergeKLists(ListNode[] lists) {
        // 构建辅助队列处理链表
        LinkedList<ListNode> queue = new LinkedList();
        for (ListNode node : lists) {
            queue.offer(node);
        }

        // 边界条件判断，如果列表为空或者只有一个的情况
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }

        // 当辅助队列中存储的链表中元素超出2个则进行合并，直到只剩下一个
        while (queue.size() >= 2) {
            // 取出两个链表进行合并，并将合并后的结果追加到队列尾部
            ListNode link1 = queue.pop();
            ListNode link2 = queue.pop();
            ListNode mergeLink = merge(link1, link2);
            queue.offer(mergeLink);
        }

        // 最终返回队列中剩下的那个合并链表
        return queue.pop();
    }

    // 合并两个有序链表
    public ListNode merge(ListNode link1, ListNode link2) {
        // 构建虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        // 定义两个待合并链表的遍历指针
        ListNode pointer1 = link1;
        ListNode pointer2 = link2;

        // 遍历链表
        while (pointer1 != null && pointer2 != null) {
            // 选择较小的元素加入
            int val1 = pointer1.val;
            int val2 = pointer2.val;
            if (val1 <= val2) {
                // 加入新节点
                cur.next = new ListNode(val1);
                // 指针后移
                cur = cur.next;
                pointer1 = pointer1.next;
            } else {
                // 加入新节点
                cur.next = new ListNode(val2);
                // 指针后移
                cur = cur.next;
                pointer2 = pointer2.next;
            }
        }
        // 拼接剩余的链表
        if (pointer1 != null) {
            cur.next = pointer1;
        }
        if (pointer2 != null) {
            cur.next = pointer2;
        }

        // 返回构建的链表
        return dummy.next;
    }
}

• 复杂度分析

  • 时间复杂度：O（N）N 为所有链表的节点总和（需要遍历所有的链表节点）

  • 空间复杂度：O（N）每次两两合并需要维护一个合并后的链表，最终得到完全合并的链表。此外需额外的队列维护链表集合

👻方法2：最小堆（辅助集合+构建新链表）

• 思路分析：最小堆
  • （1）初始化将所有链表的头节点入堆（K个链表则对应K个头节点）
  • （2）合并后的链表的头节点一定是某个链表的头节点，而最小堆的堆顶元素一定是最小的，因此可以通过遍历这个最小堆来达到目的（本质上可以理解为是遍历所有的链表节点入最小堆，然后依次弹出构建新链表）
    • 采用取一个放一个的思路，取出当前小顶堆的最小元素，如果该节点存在next则需将其next入堆等待下一次循环判断，将取出来的节点拼入新链表即可
• 补充说明
  • 最硬核的遍历思路是：遍历链表中的所有节点放在一个集合中，然后对这个集合的元素进行排序，然后构建新链表
  • 最小堆的集合的思路，一方面是使用了最小堆的特性（不需要手动判断排序），另一方面是在遍历的过程中并不是直接将所有链表的节点都入堆，而是取一个放一个的思路，例如取出某个堆顶节点，如果其存在next则说明该链表还没遍历完成，在取出的同时要将next节点入堆用作下次循环比较。基于这种设定，小顶堆始终存储着K个节点，大大节省了空间

/**
 * 023 合并K个有序链表
 */
public class Solution2 {

    // 思路：最小堆（辅助集合+构建新链表）
    public ListNode mergeKLists(ListNode[] lists) {
        // 定义虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy; // 新链表指针

        // 构建最小堆：将所有链表的头节点入堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a,b)->a.val-b.val); // 排序规则限定
        for(ListNode node : lists){
            if(node!=null){
                heap.add(node);
            }
        }

        // 遍历堆中元素
        while(!heap.isEmpty()){
            // 依次弹出堆中节点（如果其next存在则需要将其next节点入堆）
            ListNode node = heap.poll();
            if(node.next!=null){
                // 表示当前这个链表还不为空，需要将其next节点入堆
                heap.add(node.next);
            }

            // 构建链表
            cur.next = new ListNode(node.val);
            cur = cur.next; // 指针后移
        }

        // 返回结果
        return dummy.next;
    }
}

• 复杂度分析

  • 时间复杂度：O(nlogk)，其中 k 为 lists 的长度，n 为所有链表的节点数之和

  • 空间复杂度：O（K）小顶堆设定最多占用K个ListNode节点的空间