经典150题 - 分治

108. 将有序数组转换为二叉搜索树

var sortedArrayToBST = function(nums) {
    const build = (left, right) => {   // 左闭右闭区间 [left, right]
        if (left > right) {
            return null
        }
        const mid = Math.floor((right - left) / 2) + left
        return new TreeNode(nums[mid], build(left, mid - 1), build(mid + 1, right))
    }
 
    return build(0, nums.length - 1)
};

• 时间复杂度：O(n)，每个元素恰好建一个节点，mid 位置不重复访问
• 空间复杂度：O(log n)，平衡树递归深度（不算返回的树本身）

关键套路：分治三步——分：中点为根，数组被切成左段+根+右段；治：左右段递归建树（与原问题同构）；合：接上 root.left / root.right。

两个约束各自被什么保证：

• BST 性质 ← 数组的有序性：mid 左边的元素全小于它，右边全大于它，递归下去每层都成立，不需要额外检查
• 平衡 ← 取中点：左右段长度差 ≤ 1，左右子树又各自平衡（归纳），故高度差 ≤ 1；取上中点 Math.ceil 同样成立

注意点：

1. 加区间参数后 mid 必须以 left 为锚：left + Math.floor((right - left) / 2)，直接 Math.floor((right - left) / 2) 会算出区间内偏移而非数组下标（与二分查找同一模板）
2. 不用 slice 切新数组，传下标区间即可——slice 版每层复制 O(n)、共 O(log n) 层，退化成 O(n log n)；与 230. 二叉搜索树中第 K 小的元素「移动下标不复制数据」同一手法
3. 左闭右闭约定三处自洽：空区间 left > right、左递归 (left, mid - 1)、右递归 (mid + 1, right)；若用左闭右开 [left, right)，则空区间为 left === right、左递归 (left, mid)，两套约定不可混用

148. 排序链表

const merge = (left, right) => {   // [21. 合并两个有序链表] 原样复用，节点直接拼接
    const dummy = new ListNode()
    let p = dummy
    while (left && right) {
        if (left.val < right.val) {
            p.next = left
            left = left.next
        } else {
            p.next = right
            right = right.next
        }
        p = p.next
    }
    p.next = left || right
    return dummy.next
}
 
var sortList = function (head) {
    if (!head?.next) return head          // 出口：空链表或单节点，天然有序
    let slow = head
    let fast = head.next                  // 起步错位一步，让 slow 停在前半段尾部
    while (fast?.next) {
        slow = slow.next
        fast = fast.next.next
    }
    const right = slow.next               // 先抓右半段头，再断链（顺序不能反）
    slow.next = null
    return merge(sortList(head), sortList(right))
};

• 时间复杂度：O(n log n)，归并排序：每层合并 O(n)，共 O(log n) 层；这是题目对时间的要求，直接排除插入/选择排序等 O(n²) 做法
• 空间复杂度：O(log n)，递归栈深度（平衡切分）

关键套路：归并排序 = 分治。分：快慢指针找中点 + 断链；治：左右两半递归排序；合：21 题的 dummy 迭代合并。快慢指针、合并有序链表、分治三件已有武器的组合题。

注意点：

1. 出口必须同时挡住空链表和单节点 !head?.next——单节点若继续切分，left 永远是原链表，无限递归（对应 108 的空区间出口）
2. fast 起步必须错位 head.next：若 fast = head，两节点链表 slow 会停在尾部，切完 left 和原链表一模一样 → 无限递归
3. fast 只是跑腿的，循环结束的落点没有语义（跳两步可能跨过节点、甩掉中间节点）；右半段头部只能取 slow.next，且必须先抓取再断链，反过来拿到的是 null
4. 合并复用 21 题，p.next = left || right 一行接管剩余段，不开新节点

变体：23. 合并 K 个升序链表（分治两两合并，把本题的 merge 当积木用）；进阶 O(1) 空间可用自底向上迭代归并（bottom-up），无递归栈。

相关笔记

• 二叉搜索树专题
• 二叉树其他题目
• 链表专题
• 树与二叉树基础
• 链表基础