分治

副标题 / 摘要 LeetCode 105 的关键不是死记“前序 + 中序能构树”，而是先看懂两种遍历各自提供什么信息。前序负责告诉你谁是根，中序负责告诉你左右边界，组合起来就能自然落成一个哈希定位的区间分治。 预计阅读时长：12~15 分钟 标签：Hot100、二叉树、分治、哈希表、前序遍历 SEO 关键词：Construct Binary Tree from Preorder and Inorder Traversal, 从前序与中序遍历序列构造二叉树, 前序遍历, 中序遍历, 分治, LeetCode 105 元描述：系统讲透 LeetCode 105 的构树推导、索引分治、哈希优化与多语言实现，并解释为什么一定要先建左子树。 A — Algorithm（题目与算法） 题目还原 给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder，请你重建这棵二叉树并返回它的根节点。 题目保证： 树中元素没有重复 给出的两个数组一定来自同一棵合法二叉树 输入输出 名称 类型 描述 preorder int[] 前序遍历结果 inorder int[] 中序遍历结果 返回值 TreeNode 重建后的二叉树根节点 示例 1 输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出：[3,9,20,null,null,15,7] 示例 2 输入：preorder = [-1], inorder = [-1] 输出：[-1] 提示 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder 都没有重复元素 inorder 中的每个值都出现在 preorder 中 preorder 保证是某棵树的前序遍历 inorder 保证是同一棵树的中序遍历 目标读者 一看到“根据遍历结果构树”就会混淆前序和中序职责的学习者 想把“树的遍历顺序”和“树的结构恢复”建立稳定联系的开发者 做过 94、114 之后，想继续巩固树结构题的读者 背景 / 动机 这题最值得学的地方是： ...

副标题 / 摘要 LeetCode 108 的关键不在“会递归”，而在于看懂题目同时要求两件事：既要保持 BST 的有序性，又要尽量平衡。只要抓住“中点做根”这个证据，整题就会自然落成一个非常干净的区间分治。 预计阅读时长：11~14 分钟 标签：Hot100、二叉树、BST、分治、递归 SEO 关键词：Convert Sorted Array to Binary Search Tree, 将有序数组转换为二叉搜索树, 平衡二叉搜索树, BST, 分治, LeetCode 108 元描述：系统讲透 LeetCode 108 的中点分治构造法，覆盖题意推导、正确性解释、工程映射与多语言实现。 A — Algorithm（题目与算法） 题目还原 给你一个严格递增的整数数组 nums，请把它转换成一棵高度平衡的二叉搜索树。 这里同时包含两个目标： 新树必须满足 BST 的大小关系 新树还必须尽量平衡，也就是任意节点左右子树高度差不超过 1 输入输出 名称 类型 描述 nums int[] 严格递增数组 返回值 TreeNode 任意一棵合法的高度平衡 BST 根节点 示例 1 输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也同样正确。 示例 2 输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。 提示 1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums 按严格递增顺序排列 目标读者 正在刷 Hot100，希望把“数组转树”的分治模板固定下来的学习者 已经会写 BST 判断，但还不够熟悉“BST 构造题”如何从题意推出来的开发者 想理解为什么“中点做根”不是技巧，而是由约束直接逼出来的读者 背景 / 动机 这题很适合拿来训练一个能力： ...

副标题 / 摘要 LeetCode 148 的核心不是“会排序”，而是“在链表结构里选对排序算法”。数组可随机访问适合快排/堆排，而单链表最匹配的是归并排序：找中点、递归分治、线性归并。 预计阅读时长：12~16 分钟 标签：Hot100、链表、归并排序、分治 SEO 关键词：Sort List, 排序链表, 链表归并排序, LeetCode 148, Hot100 元描述：用链表归并排序在 O(n log n) 内完成排序，覆盖思路推导、工程迁移、复杂度分析和多语言可运行实现。 A — Algorithm（题目与算法） 题目还原 给你链表头节点 head，请将其按升序排序并返回排序后的链表。 要求时间复杂度为 O(n log n)。 输入输出 名称 类型 描述 head ListNode 单链表头节点（可能为空） 返回 ListNode 升序排序后的头节点 示例 1 输入: 4 -> 2 -> 1 -> 3 输出: 1 -> 2 -> 3 -> 4 示例 2 输入: -1 -> 5 -> 3 -> 4 -> 0 输出: -1 -> 0 -> 3 -> 4 -> 5 目标读者 正在刷 Hot100，想把链表题模板系统化的同学 做链表题经常在“切分和拼接”环节出错的开发者 想搞清楚“为什么链表排序优先用归并”而不是快排的人 背景 / 动机 链表排序在工程里并不罕见： ...

副标题 / 摘要 这题本质是“k 路归并”。如果直接一条条串行并入，性能会退化；用分治按二叉树方式两两合并，能把复杂度优化到 O(N log k)。本文按 ACERS 模板把思路推导、工程映射和多语言实现一次讲透。 预计阅读时长：12~16 分钟 标签：Hot100、链表、分治、归并 SEO 关键词：Merge k Sorted Lists, 合并K个升序链表, 分治归并, LeetCode 23, O(N log k) 元描述：从串行归并到分治归并，系统讲解 LeetCode 23 的最优复杂度解法与工程实践。 A — Algorithm（题目与算法） 题目还原 给你一个链表数组 lists，每个链表都按升序排列。 请将所有链表合并到一个升序链表中，并返回合并后的头节点。 输入输出 名称 类型 描述 lists ListNode[] k 条升序链表，元素可为空 返回 ListNode 合并后的升序链表头节点 示例 1 输入: lists = [[1,4,5],[1,3,4],[2,6]] 输出: [1,1,2,3,4,4,5,6] 示例 2 输入: lists = [] 输出: [] 目标读者 正在刷 Hot100，已经掌握 LeetCode 21 的同学 想把“双链表归并”升级为“k 路归并模板”的开发者 在服务端做多路有序流合并（日志、时间线、分片结果）的工程师 背景 / 动机 LeetCode 23 是 LeetCode 21 的自然升级版： ...