有序链表转高度平衡二叉搜索树实现

有序链表转换成二叉搜索树是一种常见的数据结构问题，涉及到链表和二叉树的相互转换。题目中给出的单链表元素已按照升序排列，目标是构建一棵高度平衡的二叉搜索树。在二叉搜索树中，每个节点的值大于其左子树中所有节点的值，且小于其右子树中所有节点的值。高度平衡意味着任意节点的左右子树高度差的绝对值不超过1。 首先，我们分析一下题目的核心算法步骤： 1. **链表长度计算**: 在`Solution`类中，`getLength`函数用于计算链表的长度。通过遍历链表，逐个节点计数，直到遍历到链表末尾，返回节点总数。 2. **递归构建二叉搜索树**: `buildTree`函数是实现核心转换的关键。该函数接受四个参数：当前链表指针`head`，以及需要分割的左边界`left`和右边界`right`。当左边界大于右边界时，说明已经到达链表的末尾，返回`nullptr`表示空节点。 - 计算中间索引`mid`，确保它将链表平均分为两部分。 - 创建一个新的`TreeNode`对象作为当前层的根节点。 - 递归调用`buildTree`，分别构建左子树（`root->left`）和右子树（`root->right`），左子树处理左半部分链表，右子树处理右半部分链表。 - 将当前链表指针`head`移动到下一个节点，因为已经将当前节点添加到了二叉树中。 3. **整体转换函数**: `sortedListToBST`是主入口函数，它调用`getLength`获取链表长度，然后根据链表长度和二分查找的思想调用`buildTree`函数，从头开始构建整个高度平衡的二叉搜索树。 解决这个问题的策略是利用链表的有序性，采用分治法，每次划分链表的一半来构建二叉树，确保最终得到的二叉搜索树是平衡的。这种转换方法可以高效地将有序链表转化为满足特定条件的二叉搜索树。在实际编程中，`Solution`类中的这些函数组合起来可以实现这一功能，并在时间复杂度上达到O(n)的效率。