Leetcode 142 将有序数组转换为二叉搜索树 | 排序链表

1 题目108. 将有序数组转换为二叉搜索树给你一个整数数组nums其中元素已经按升序排列请你将其转换为一棵 平衡 二叉搜索树。示例 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 104-104 nums[i] 104nums按严格递增顺序排列2 代码实现c/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private: TreeNode* buildBST(vectorint nums, int l ,int r ){ if (l r ){ return nullptr; } int mid l (r - l ) / 2 ; TreeNode* root new TreeNode(nums[mid]); root - left buildBST(nums, l , mid -1 ); root - right buildBST(nums, mid 1 , r ); return root ; } public: TreeNode* sortedArrayToBST(vectorint nums) { return buildBST(nums , 0 , nums.size() - 1 ) ; } };js/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } */ /** * param {number[]} nums * return {TreeNode} */ var sortedArrayToBST function(nums) { const buildBST (l, r ) { if (l r ) return null ; const mid l Math.floor((r - l ) / 2 ); const root new TreeNode(nums[mid]); root.left buildBST(l , mid - 1 ); root.right buildBST(mid 1, r ); return root ; }; return buildBST(0, nums.length - 1); };思考我隐约记得二叉搜索树的中序遍历就是有序数组。。然后呢怎么返回去构造题解问题分析与解题思路要将升序数组转换为平衡二叉搜索树BST核心思路是利用 BST 和平衡树的特性BST 特性中序遍历结果为升序数组因此数组的中间元素作为根节点左半部分为左子树右半部分为右子树。平衡特性每次选择数组中点作为根节点能保证左右子树的节点数差不超过 1天然满足平衡要求。具体步骤找到当前数组的中间元素作为当前子树的根节点。递归处理左半数组构建左子树。递归处理右半数组构建右子树。返回当前根节点。完整 C 代码实现#include vector using namespace std; // 定义二叉树节点结构LeetCode默认定义 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { // 调用递归函数初始范围是整个数组[0, nums.size()-1] return buildBST(nums, 0, nums.size() - 1); } private: // 递归构建BST参数为数组、当前处理区间的左边界l、右边界r TreeNode* buildBST(vectorint nums, int l, int r) { // 递归终止条件左边界 右边界说明当前区间无元素返回空节点 if (l r) { return nullptr; } // 选择中间位置作为根节点整数除法向下取整也可以用(l r 1)/2选右中点结果也正确 int mid l (r - l) / 2; // 等价于(lr)/2避免溢出 // 创建当前根节点 TreeNode* root new TreeNode(nums[mid]); // 递归构建左子树左区间[l, mid-1] root-left buildBST(nums, l, mid - 1); // 递归构建右子树右区间[mid1, r] root-right buildBST(nums, mid 1, r); // 返回当前根节点 return root; } }; // 测试代码可选用于验证 #include iostream // 中序遍历验证BST特性结果应与输入数组一致 void inorderTraversal(TreeNode* root) { if (root nullptr) return; inorderTraversal(root-left); cout root-val ; inorderTraversal(root-right); } int main() { vectorint nums {-10, -3, 0, 5, 9}; Solution sol; TreeNode* root sol.sortedArrayToBST(nums); // 中序遍历输出-10 -3 0 5 9验证BST正确性 inorderTraversal(root); return 0; }代码关键部分解释递归终止条件if (l r) return nullptr当区间无元素时返回空节点结束当前递归分支。中间节点选择int mid l (r - l) / 2避免直接用(l r) / 2导致整数溢出比如 l 和 r 都是大数时同时保证每次选中点作为根满足平衡要求。递归构建子树左子树处理[l, mid-1]区间对应数组左半部分值都小于根节点符合 BST 左子树值更小的特性。右子树处理[mid1, r]区间对应数组右半部分值都大于根节点符合 BST 右子树值更大的特性。测试验证通过中序遍历输出结果若与输入升序数组一致说明 BST 构建正确平衡特性由 “选中点” 的逻辑天然保证。总结核心逻辑利用升序数组的中点作为根节点递归构建左右子树既满足 BST 的中序遍历特性又保证平衡左右子树高度差≤1。关键细节选择中点时用l (r - l)/2避免溢出递归终止条件是区间无元素l r。灵活性中点也可选择(l r 1)/2右中点最终结果不同但仍满足 “平衡 BST” 要求如示例中两种答案均正确。js版本问题分析与解题思路JS 版核心思路和 C 版本完全一致利用升序数组 中点作为根节点的特性递归构建平衡二叉搜索树BST。BST 特性中序遍历是升序数组因此中点为根左半数组构建左子树右半数组构建右子树。平衡特性每次选中点作为根左右子树节点数差≤1天然满足平衡要求。完整 JavaScript 代码实现// 定义二叉树节点类模拟LeetCode的TreeNode结构 class TreeNode { constructor(val, left null, right null) { this.val val; this.left left; this.right right; } } /** * param {number[]} nums * return {TreeNode} */ var sortedArrayToBST function(nums) { // 递归构建BST的辅助函数 const buildBST (l, r) { // 递归终止条件左边界 右边界无元素可构建返回null if (l r) return null; // 计算中点避免(l r)溢出JS中数字范围大但习惯用这种写法 const mid l Math.floor((r - l) / 2); // 创建当前根节点 const root new TreeNode(nums[mid]); // 递归构建左子树左区间[l, mid-1] root.left buildBST(l, mid - 1); // 递归构建右子树右区间[mid1, r] root.right buildBST(mid 1, r); // 返回当前根节点 return root; }; // 初始调用处理整个数组[0, nums.length-1] return buildBST(0, nums.length - 1); }; // 测试代码验证功能 // 中序遍历验证BST特性输出应与输入数组一致 const inorderTraversal (root) { const res []; const traverse (node) { if (!node) return; traverse(node.left); res.push(node.val); traverse(node.right); }; traverse(root); return res; }; // 测试示例1 const nums1 [-10, -3, 0, 5, 9]; const root1 sortedArrayToBST(nums1); console.log(inorderTraversal(root1)); // 输出[-10, -3, 0, 5, 9] // 测试示例2 const nums2 [1, 3]; const root2 sortedArrayToBST(nums2); console.log(inorderTraversal(root2)); // 输出[1, 3]代码关键部分解释TreeNode 类模拟 LeetCode 中二叉树节点的结构包含val节点值、left左子节点、right右子节点三个属性。递归辅助函数buildBST参数l/r当前处理数组的左 / 右边界闭区间避免频繁切割数组提升性能。终止条件l r时返回null表示当前区间无元素结束递归。中点计算Math.floor((r - l) / 2)保证取整数中点JS 中除法会返回浮点数需向下取整。测试验证inorderTraversal函数通过中序遍历输出节点值结果应与输入升序数组一致验证 BST 构建正确平衡特性由 “选中点” 逻辑天然保证。总结核心逻辑JS 版本和 C 版本思路完全一致通过递归选数组中点作为根节点分别构建左右子树。JS 特有细节需手动定义TreeNode类除法后用Math.floor取整避免浮点数问题。性能优化通过边界索引l/r而非切割数组减少数组拷贝开销时间复杂度O(n)每个节点构建一次空间复杂度O(logn)递归栈深度平衡树的高度。3 题目148. 排序链表给你链表的头结点head请将其按升序排列并返回排序后的链表。示例 1输入head [4,2,1,3]输出[1,2,3,4]示例 2输入head [-1,5,3,4,0]输出[-1,0,3,4,5]示例 3输入head []输出[]提示链表中节点的数目在范围[0, 5 * 104]内-105 Node.val 105进阶你可以在O(n log n)时间复杂度和常数级空间复杂度下对链表进行排序吗4 代码实现c/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { private: ListNode* findMid (ListNode* head ){ if (head nullptr || head - next nullptr){ return head ; } ListNode* slow head ; ListNode* fast head - next ; while (fast ! nullptr fast - next ! nullptr ){ slow slow - next ; fast fast - next - next ; } return slow ; } ListNode* merge (ListNode* l1, ListNode* l2 ){ ListNode* dummy new ListNode(0); ListNode* cur dummy ; while (l1 ! nullptr l2 ! nullptr){ if (l1 - val l2 - val ){ cur - next l1 ; l1 l1 - next ; }else { cur - next l2 ; l2 l2 - next ; } cur cur - next ; } cur - next (l1 ! nullptr )? l1 : l2 ; ListNode* res dummy - next ; delete dummy ; return res ; } public: ListNode* sortList(ListNode* head) { if (head nullptr || head - next nullptr){ return head ; } ListNode* mid findMid(head); ListNode* rightHead mid - next ; mid - next nullptr ; ListNode* left sortList(head); ListNode* right sortList(rightHead); return merge(left ,right); } };js/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } */ /** * param {ListNode} head * return {ListNode} */ var sortList function(head) { if (head null || head.next null) { return head; } const midNode findMiddle(head); const rightHead midNode.next; midNode.next null; const leftSorted sortList(head); const rightSorted sortList(rightHead); return mergeTwoSortedLists(leftSorted, rightSorted); }; /** * param {ListNode} head * return {ListNode} */ function findMiddle(head) { if (head null || head.next null) { return head; } let slow head; let fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; } /** * param {ListNode} l1 * param {ListNode} l2 * return {ListNode} */ function mergeTwoSortedLists(l1, l2) { const dummy new ListNode(-1); let current dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { current.next l1; l1 l1.next; } else { current.next l2; l2 l2.next; } current current.next; } current.next l1 ! null ? l1 : l2; return dummy.next; }思考如果是数组就很简单了可是这是链表各种指针要改怎么办呢我说实话这个对我又太难了。题解分治的核心思路和数组的归并排序完全一致只是链表的 “分割” 需要用快慢指针找中点而不是直接索引分Divide用快慢指针找到链表中点将链表拆分为左右两个子链表治Conquer递归排序左右两个子链表合Merge将两个排序好的子链表合并为一个有序链表。完整 C 代码分治版归并排序#include iostream #include vector using namespace std; // 链表节点定义LeetCode默认 struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: ListNode* sortList(ListNode* head) { // 递归终止条件空链表 或 只有一个节点天然有序 if (head nullptr || head-next nullptr) { return head; } // 1. 分找中点拆分链表为左、右两部分 ListNode* mid findMid(head); ListNode* rightHead mid-next; mid-next nullptr; // 切断链表分为 [head, mid] 和 [rightHead, ...] // 2. 治递归排序左、右子链表 ListNode* left sortList(head); ListNode* right sortList(rightHead); // 3. 合合并两个有序子链表 return merge(left, right); } private: // 快慢指针找链表中点关键慢指针最终停在中间偏左的节点 ListNode* findMid(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* slow head; // 慢指针每次走1步 ListNode* fast head-next; // 快指针每次走2步这样拆分后左右更均衡 while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; // 最终slow指向链表中点偶数长度时指向中间偏左 } // 合并两个有序链表和之前的merge函数完全一致经典逻辑 ListNode* merge(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); // 虚拟头节点简化合并逻辑 ListNode* cur dummy; // 逐个比较两个链表的节点取较小值接入结果 while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } // 拼接剩余未处理的节点l1或l2可能还有剩余 cur-next (l1 ! nullptr) ? l1 : l2; ListNode* res dummy-next; delete dummy; // 释放虚拟节点避免内存泄漏 return res; } }; // 测试代码和之前一致方便验证 void printList(ListNode* head) { while (head ! nullptr) { cout head-val ; head head-next; } cout endl; } ListNode* createList(vectorint nums) { ListNode* dummy new ListNode(0); ListNode* cur dummy; for (int num : nums) { cur-next new ListNode(num); cur cur-next; } ListNode* res dummy-next; delete dummy; return res; } int main() { vectorint nums1 {4,2,1,3}; ListNode* head1 createList(nums1); Solution sol; ListNode* sortedHead1 sol.sortList(head1); printList(sortedHead1); // 输出1 2 3 4 vectorint nums2 {-1,5,3,4,0}; ListNode* head2 createList(nums2); ListNode* sortedHead2 sol.sortList(head2); printList(sortedHead2); // 输出-1 0 3 4 5 return 0; }关键部分拆解新手友好版1. 找中点快慢指针的核心逻辑为什么用fast head-next而不是fast head如果用fast head偶数长度链表如 4 个节点的中点会偏右拆分后左链表更长可能导致递归深度增加用fast head-next偶数长度时中点偏左比如 4 个节点时slow 停在第 2 个节点拆分后左右链表长度更均衡。举个例子链表4→2→1→3slow 初始 4fast 初始 2第一次循环slow2fast3fast-nextnull循环结束slow2中点拆分后左链表4→2右链表1→3。2. 递归的 “分 - 治 - 合” 过程以 [4,2,1,3] 为例初始sortList(4→2→1→3) 分找中点2拆分为 4→2 和 1→3 治 sortList(4→2) 分找中点4拆分为4 和 2 治sortList(4)4sortList(2)2 合merge(4,2) → 2→4 sortList(1→3) 分找中点1拆分为1 和 3 治sortList(1)1sortList(3)3 合merge(1,3) → 1→3 合merge(2→4, 1→3) → 1→2→3→43. 合并两个有序链表最核心的基础操作比如合并2→4和1→3dummy 初始 0cur0比较 2 和 1 → cur-next1cur1l23比较 2 和 3 → cur-next2cur2l14比较 4 和 3 → cur-next3cur3l2null拼接剩余的 4 → cur-next4最终返回 dummy-next → 1→2→3→4。总结分治核心用快慢指针找中点拆分链表分递归排序子链表治合并有序子链表合关键技巧快慢指针找中点是链表分治的核心虚拟头节点简化合并操作复杂度时间 O (n log n)和自底向上版一致空间 O (log n)递归栈深度平衡拆分时栈深度为 log n。这个版本虽然空间复杂度略高但逻辑更直观先理解这个版本再回头看自底向上版会容易很多。你可以先把 “找中点” 和 “合并有序链表” 这两个基础操作练熟再结合递归整个逻辑就通了。嘶好复杂不想看。其实就是先分拆两个链表然后再转化成合并两个链表内部排序呢怎么做万一最小的在尾部呢你这个问题问到了核心很多新手都会疑惑拆分后的子链表本身是无序的怎么保证合并后整体有序最小的元素在尾部排序能覆盖到吗答案很简单递归的「治」阶段会把链表拆到「最小粒度」单个节点单个节点天然有序再通过「合」阶段的合并操作从最小的有序单元开始层层合并成更大的有序链表。1. “内部排序” 是怎么实现的—— 拆到最小单元再合并你担心 “最小的元素在尾部”但递归会把链表拆到只剩一个节点此时每个节点都是 “有序链表”只有自己合并时会从这些最小单元开始把小的元素优先拼接自然能覆盖到尾部的最小值。举个极端例子链表[5,4,3,2,1]最小值 1 在尾部我们一步步看递归怎么处理初始sortList(5→4→3→2→1) 分找中点3 → 拆分为 5→4→3 和 2→1 治 处理 5→4→3 分找中点4 → 拆分为 5→4 和 3 治 处理 5→4 分找中点5 → 拆分为 5 和 4 治5有序、4有序 合merge(5,4) → 4→5 处理 33有序 合merge(4→5, 3) → 3→4→5 处理 2→1 分找中点2 → 拆分为 2 和 1 治2有序、1有序 合merge(2,1) → 1→2 合merge(3→4→5, 1→2) → 1→2→3→4→5你看最小值 1 在最开始的链表尾部但递归拆到单个节点后合并时会先比较 1 和 2把 1 放在前面最终合并 3→4→5 和 1→2 时又会把 1→2 放在最前面完全覆盖到尾部的最小值。2. 为什么拆分到单个节点就够了单个节点没有 “内部元素”本身就是有序的这是递归的终止条件合并操作的核心是「把两个有序链表合并成一个有序链表」—— 只要输入的两个子链表是有序的合并后的结果就一定有序递归的过程就是 “拆到最小有序单元 → 合并成更大的有序单元 → 最终合并成完整有序链表”。用 “可视化流程” 帮你理解以 [5,4,3,2,1] 为例我们用 “拆分→最小有序单元→合并” 的流程看最小值 1 怎么被找出来拆分阶段分最小有序单元治合并阶段合5→4→3→2→1 → 5→4→3 2→1--5→4→3 → 5→4 32→1 → 2 1--5→4 → 5 45有序、4有序、3有序、2有序、1有序---54 → 4→521 → 1→2--4→5 3 → 3→4→5--3→4→5 1→2 → 1→2→3→4→5关键合并函数的 “有序性保证”合并两个有序链表的函数mergeTwoSortedLists是整个排序的 “核心发动机”它的逻辑决定了只要输入的两个链表是有序的输出一定是有序的。再拆解合并函数的逻辑以合并3→4→5和1→2为例dummy -1current -1 l1 3→4→5l2 1→2 第一步比较 3 和 1 → current.next 1current1l22 第二步比较 3 和 2 → current.next 2current2l2null 第三步l2 为空拼接 l1 剩余节点 → current.next 3→4→5 最终结果1→2→3→4→5哪怕 l1 是3→4→5整体比 l2 大合并函数也会先把 l2 的所有小元素拼在前面完全覆盖 “最小值在另一个链表” 的情况。总结回答你的核心疑问内部排序的本质不是 “直接给无序链表内部排序”而是通过递归把链表拆成单个节点天然有序再通过合并操作从最小有序单元开始层层拼接成有序链表最小值在尾部也能覆盖拆分到单个节点后最小值会变成一个独立的有序单元合并时会被优先比较并放在前面核心保证合并函数能保证 “两个有序输入 → 一个有序输出”递归的层层合并最终让整个链表有序。简单记拆到不能再拆单个节点合到不能再合完整链表—— 这就是归并排序的核心不管是数组还是链表逻辑完全一致只是链表拆分需要用快慢指针而已。5 小结对我来说有点难了明天清醒的时候再回头看看。。。分治。