0109. Convert Sorted List to Binary Search Tree =============================================== 题目信息 -------- :题号: 0109. 有序链表转换二叉搜索树 :难度: Medium :主题: 链表、二叉搜索树、分治、中序模拟 :原题: `LeetCode 0109 `_ :重点: 识别链表缺少随机访问这一瓶颈,用中序构造顺序让单向游标恰好在需要根值时到达中点 题目重述 -------- 给定一个按非递减顺序排列的单链表 ``head``,构造并返回一棵高度平衡的二叉搜索树。输出树的中序值序列应 与链表值序列一致;高度平衡表示每个节点的左右子树高度差不超过 ``1``。 链表为空时返回空树,满足要求的树结构可能不唯一。节点总数在 ``0..2 * 10^4`` 范围内,节点值在 ``-10^5..10^5`` 范围内。算法只读取链表,不修改原有 ``next`` 关系。 自建示例 -------- * 奇数长度:``head = [-6,-1,2,7,13]``,一种合法层序结果为 ``[2,-1,13,-6,null,7]``; * 偶数长度:``head = [1,3,5,7]``,选择 ``5`` 为根可得到 ``[5,3,7,1]``,选择另一个中点也可合法; * 单节点:``head = [4]``,返回只含节点 ``4`` 的树; * 空链表:``head = []``,返回空树。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: TreeNode* buildFromArray(const std::vector& values, int left, int right) { if (left > right) { return nullptr; } const int middle = left + (right - left) / 2; TreeNode* root = new TreeNode(values[middle]); root->left = buildFromArray(values, left, middle - 1); root->right = buildFromArray(values, middle + 1, right); return root; } TreeNode* buildByFindingMiddle(ListNode* begin, ListNode* end) { if (begin == end) { return nullptr; } ListNode* slow = begin; ListNode* fast = begin; while (fast != end && fast->next != end) { slow = slow->next; fast = fast->next->next; } TreeNode* root = new TreeNode(slow->val); root->left = buildByFindingMiddle(begin, slow); root->right = buildByFindingMiddle(slow->next, end); return root; } TreeNode* buildByInorderSimulation(ListNode*& cursor, int count) { if (count == 0) { return nullptr; } const int leftCount = count / 2; TreeNode* leftRoot = buildByInorderSimulation(cursor, leftCount); TreeNode* root = new TreeNode(cursor->val); cursor = cursor->next; root->left = leftRoot; root->right = buildByInorderSimulation(cursor, count - leftCount - 1); return root; } public: TreeNode* sortedListToBST(ListNode* head) { int count = 0; for (ListNode* node = head; node; node = node->next) { ++count; } ListNode* cursor = head; return buildByInorderSimulation(cursor, count); } }; 题解 ---- 数组方法的缺口 ~~~~~~~~~~~~~~ 对有序数组,选择中点为根、递归处理左右区间,就能同时保持中序顺序和高度平衡。链表值同样有序,根也应取 当前片段的中间值;区别在于单链表只能沿 ``next`` 前进,无法通过下标在常数时间到达中点。 最直接的正确方案是先把全部值复制到数组,再调用中点分治。``buildFromArray`` 的每个状态都能随机访问 ``values[middle]``,构造时间为 ``O(n)``;但转换数组额外保存了整份 ``O(n)`` 值,而返回树最终只需要这些 值各出现一次。 重复寻找中点 ~~~~~~~~~~~~ 若不使用数组,可以把子链表表示为半开区间 ``[begin, end)``,每次用快慢指针找到中点。``fast`` 每次走 两步、``slow`` 每次走一步;快指针抵达边界时,慢指针位于中间节点。根左侧区间为 ``[begin, slow)``, 右侧区间为 ``[slow->next, end)``。 ``buildByFindingMiddle`` 不复制值,也不切断链表,因此空间状态很小。然而每层递归都要从当前区间开头重新走 到中点。树被中点划分得近似平衡,每个递归层合计扫描 ``O(n)`` 个链表节点,共 ``O(log n)`` 层,总时间 为 ``O(n log n)``。瓶颈是为获得随机访问效果而重复顺序扫描。 构造顺序转换 ~~~~~~~~~~~~ 最终树的中序遍历必须按链表顺序出现。与其先找根再构造孩子,可以反过来模拟中序构造过程:先构造左子树, 再用当前链表节点创建根,最后构造右子树。这样链表游标始终只向前走。 定义 ``build(count)`` 为“从 ``cursor`` 指向的位置开始,消费接下来的 ``count`` 个链表节点,构造一棵平衡 子树”。状态按以下顺序执行: #. 左子树消费 ``leftCount = count / 2`` 个值; #. 左递归返回后,``cursor`` 指向当前区间中点,用它创建根并前进一步; #. 右子树消费剩余的 ``count - leftCount - 1`` 个值。 递归调用发生在根节点创建之前并不影响最终父子关系。左递归先返回 ``leftRoot``,根创建后再把这个指针接到 ``root->left``;构造时间顺序与树中父节点是否先存在是两回事。 游标不变量 ~~~~~~~~~~ 进入 ``build(count)`` 时,``cursor`` 指向当前子树中序序列的第一个未消费值;返回时,它恰好前进 ``count`` 次,指向下一段序列的开头。左递归按定义消费 ``leftCount`` 个节点,所以返回时游标自然落在根值, 不需要寻找中点。 对 ``[-6,-1,2,7,13]``,构造状态如下: .. list-table:: :header-rows: 1 * - 状态规模 - 左规模 - 左递归后根值 - 右规模 - 返回后下一个值 * - 5 - 2 - 2 - 2 - 链表结束 * - 左侧 2 - 1 - -1 - 0 - 2 * - 左侧 1 - 0 - -6 - 0 - -1 * - 右侧 2 - 1 - 13 - 0 - 链表结束 * - 右侧的左 1 - 0 - 7 - 0 - 13 每创建一个树节点只消费一次当前链表节点。先左、根、右的构造顺序也保证输出树的中序值序列与原链表完全 相同;无需复制值,也不会改变任何原链表节点的 ``next``。 平衡与主解 ~~~~~~~~~~ 每个 ``count`` 被拆成 ``floor(count / 2)`` 个左节点、一个根和余下右节点,两侧规模差最多 ``1``。两侧又 递归执行同样划分,因此构造高度为 ``O(log n)``,每个节点的左右子树高度差不超过 ``1``。偶数规模选择的 中点由 ``leftCount`` 决定,换另一中点也可能得到不同但合法的树。 公开入口采用中序模拟。它先用一次顺序扫描得到节点数,再用第二次顺序消费完成构造,删除了数组副本和每层 快慢指针扫描。 复杂度分析 ~~~~~~~~~~ 转数组法时间 ``O(n)``、数组工作空间 ``O(n)``;重复找中点法时间 ``O(n log n)``、递归栈 ``O(log n)``; 中序模拟的计数与构造各扫描一次,总时间 ``O(n)``,递归栈 ``O(log n)``。返回树的 ``O(n)`` 节点不计入 工作空间。