【5.10】指针算法-快慢指针将有序链表转二叉搜索树

一、题目

  -10     5

二、解题思路

        二叉搜索树具有这样的特点：当前节点大于左子树的所有节点，同时小于右子树的所有节点，并且每个节点都具备这个特性。

        题中提到，是按照升序排列的单链表，我们只需找到链表的中间节点，使其成为树的根节点。中间节点前面的部分就是根节点左子树的所有节点，中间节点后面的部分就是根节点右子树的所有节点。然后，使用递归的方式再分别对左右子树进行相同的操作……

        这里以链表 1→2→3→4→5 为例来画个图看一下。

三、代码实现

#include <iostream>
#include <vector>
#include <queue>

// 定义链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 定义树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 将有序链表转换为二叉搜索树
TreeNode* sortedListToBST(ListNode* head) {
    // 边界条件的判断
    if (head == nullptr)
        return nullptr;
    if (head->next == nullptr)
        return new TreeNode(head->val);

    // 通过快慢指针找到链表的中间结点slow，pre就是中间结点slow的前一个结点
    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* pre = nullptr;

    while (fast != nullptr && fast->next != nullptr) {
        pre = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    // 链表断开为两部分，一部分是node的左子节点，一部分是node的右子节点
    pre->next = nullptr;

    // node就是当前节点
    TreeNode* node = new TreeNode(slow->val);

    // 从head节点到pre节点是node左子树的节点
    node->left = sortedListToBST(head);

    // 从slow.next到链表的末尾是node的右子树的结点
    node->right = sortedListToBST(slow->next);

    return node;
}

// 打印树的层序遍历结果
void printTreeLevelOrder(TreeNode* root) {
    if (root == nullptr)
        return;

    std::queue<TreeNode*> q;
    q.push(root);
    bool first = true;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();

            if (!first) {
                std::cout << ", ";
            }
            first = false;

            if (node != nullptr) {
                std::cout << node->val;
                q.push(node->left);
                q.push(node->right);
            } else {
                std::cout << "null";
            }
        }
    }
    std::cout << std::endl;
}

// 创建链表
ListNode* createLinkedList(const std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

int main() {
    // 输入给定的有序链表：[-10, -3, 0, 5, 9]
    std::vector<int> values = {-10, -3, 0, 5, 9};
    ListNode* head = createLinkedList(values);

    // 将有序链表转换为二叉搜索树
    TreeNode* root = sortedListToBST(head);

    // 打印树的层序遍历结果
    std::cout << "[";
    printTreeLevelOrder(root);
    std::cout << "]" << std::endl;

    return 0;
}