力扣第109题：将排序链表转换为二叉搜索树

题目描述

给定一个单链表，其中的元素已经按升序排列，要求将其转换为一个高度平衡的二叉搜索树。

高度平衡二叉搜索树：一个二叉搜索树，其中每个节点的左右子树的高度差的绝对值不超过1。

解题思路

为了将排序链表转换为二叉搜索树，我们可以利用二叉搜索树中节点的排列特性。

二叉搜索树的中序遍历：对于一棵二叉搜索树，中序遍历会生成一个升序排列的节点序列。因此，排序链表转换为二叉搜索树的关键是将链表的中间节点作为树的根节点。
分治法：我们可以利用递归的方式，选取链表的中间节点作为根节点，递归地构建左子树和右子树。
链表的中间节点：为了快速找到链表的中间节点，我们可以使用快慢指针（快指针一次走两步，慢指针一次走一步），直到快指针到达链表末尾时，慢指针恰好位于链表的中间。

解法步骤

使用快慢指针找到链表的中间节点。
以该节点为根节点，递归地构建左子树和右子树。
每次递归时，切分链表，使得每次只处理链表的一部分。

代码实现（C 语言）

#include <stdio.h>
#include <stdlib.h>// 定义链表节点
struct ListNode {int val;struct ListNode *next;
};// 定义二叉树节点
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 快慢指针找到链表中间节点
struct ListNode* findMiddle(struct ListNode* head) {struct ListNode *slow = head;struct ListNode *fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}return slow;
}// 递归构建二叉搜索树
struct TreeNode* sortedListToBST(struct ListNode* head) {if (head == NULL) {return NULL;}// 找到中间节点struct ListNode* mid = findMiddle(head);// 创建根节点struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = mid->val;root->left = root->right = NULL;// 如果链表中只有一个元素，则不需要递归if (head == mid) {return root;}// 递归构建左子树struct ListNode* leftList = head;struct ListNode* rightList = mid->next;struct ListNode* temp = leftList;while (temp->next != mid) {temp = temp->next;}temp->next = NULL;root->left = sortedListToBST(leftList);root->right = sortedListToBST(rightList);return root;
}// 辅助函数：打印二叉树（中序遍历）
void inorderTraversal(struct TreeNode* root) {if (root != NULL) {inorderTraversal(root->left);printf("%d ", root->val);inorderTraversal(root->right);}
}// 测试代码
int main() {struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));head->val = -10;head->next = (struct ListNode*)malloc(sizeof(struct ListNode));head->next->val = -3;head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));head->next->next->val = 0;head->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));head->next->next->next->val = 5;head->next->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));head->next->next->next->next->val = 9;head->next->next->next->next->next = NULL;struct TreeNode* root = sortedListToBST(head);inorderTraversal(root);  // 输出中序遍历结果printf("\n");return 0;
}