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

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

题目描述

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

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

解题思路

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

1. 二叉搜索树的中序遍历：对于一棵二叉搜索树，中序遍历会生成一个升序排列的节点序列。因此，排序链表转换为二叉搜索树的关键是将链表的中间节点作为树的根节点。

2. 分治法：我们可以利用递归的方式，选取链表的中间节点作为根节点，递归地构建左子树和右子树。

3. 链表的中间节点：为了快速找到链表的中间节点，我们可以使用快慢指针（快指针一次走两步，慢指针一次走一步），直到快指针到达链表末尾时，慢指针恰好位于链表的中间。

解法步骤

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

代码实现（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;
}

代码解析

1. 链表结构：ListNode 结构体定义了链表节点，包含一个值 val 和指向下一个节点的指针 next。
2. 树结构：TreeNode 结构体定义了二叉树节点，包含一个值 val 和指向左、右子树的指针 left 和 right。
3. 快慢指针查找中间节点：findMiddle 函数使用快慢指针方法，快速找到链表的中间节点。
4. 递归构建二叉搜索树：sortedListToBST 函数根据链表的中间节点递归地构建二叉搜索树。
5. 测试：在 main 函数中，我们创建了一个示例链表，并将其转换为二叉搜索树，最后进行中序遍历打印输出。

时间复杂度与空间复杂度

• 时间复杂度：$O(n)$，其中 $n$ 是链表中的节点数。每个节点都会被访问一次。
• 空间复杂度：$O(\log n)$，递归深度为树的高度，由于我们在递归时每次只处理一部分链表，因此空间复杂度为树的高度。