C语言算法-解答有序链表转换二叉搜索树算法问题的C语言实现

题目

给定一个有序链表，将其转换为一个高度平衡的二叉搜索树。这里所谓的高度平衡是指每个节点的两个子树的深度差不超过1。

引言

将有序链表转换为二叉搜索树是一种经典的二叉树问题。在这个问题中，我们需要确保二叉树的高度平衡，以便于提高搜索效率。二叉搜索树的特点是，对于每个节点，它的左子树的所有节点值都小于该节点，右子树的所有节点值都大于该节点。

算法思路

1. 找到中间节点： 为了保持树的高度平衡，我们可以通过快慢指针法找到链表的中间节点。快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针指向的节点即为中间节点。
2. 递归构建左右子树： 将中间节点作为根节点，然后递归地将左半部分链表转换为左子树，右半部分链表转换为右子树。
3. 返回根节点： 递归的基本情况是当左边部分大于右边部分时，返回空节点。

代码实现

以下是C语言中将有序链表转换为二叉搜索树的代码实现：

#include <stdio.h>
#include <stdlib.h>

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* sortedListToBST(struct ListNode* head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->next == NULL) {
        struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val = head->val;
        root->left = NULL;
        root->right = NULL;
        return root;
    }

    // 快慢指针找中间节点
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* prev = NULL;
    while (fast != NULL && fast->next != NULL) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    // 中间节点作为根节点
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = slow->val;

    // 断开链表，递归构建左右子树
    prev->next = NULL;
    root->left = sortedListToBST(head);
    root->right = sortedListToBST(slow->next);

    return root;
}

算法分析

• 时间复杂度： 快慢指针法找到中间节点的时间复杂度是O(n)，其中n是链表的长度。在每次递归调用中，我们都需要遍历链表的一部分，因此总的时间复杂度是O(nlogn)。
• 空间复杂度： 递归调用的堆栈深度最多为log(n)，因此空间复杂度是O(logn)。

示例和测试

int main() {
    // 构造有序链表: -10 -> -3 -> 0 -> 5 -> 9
    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);
    // 此处可以编写遍历树的代码，进行验证
    return 0;
}

总结

通过快慢指针法找到链表的中间节点，然后递归地构建左右子树，我们可以将有序链表转换为一个高度平衡的二叉搜索树。这个算法的时间复杂度是O(nlogn)，空间复杂度是O(logn)。在实际应用中，这种方法可以高效地构建二叉搜索树，用于快速的搜索、插入和删除操作。