Convert Sorted List to BST - Chuyển danh sách liên kết đã sắp xếp thành cây BST cân bằng

Cho danh sách liên kết đơn các phần tử tăng dần. Chuyển thành cây tìm kiếm nhị phân (BST) cân bằng chiều cao.

Ví dụ: [-10, -3, 0, 5, 9] → cây BST cân bằng.

Giải thuật (Đệ quy tìm giữa - Fast/Slow Pointer)

Tìm nút giữa của danh sách (dùng con trỏ nhanh/chậm). Nút giữa làm gốc. Đệ quy xây dựng cây con trái từ nửa đầu, cây con phải từ nửa sau. Ngắt liên kết tại nút giữa để chia danh sách.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int data) { val = data; next = NULL; }
};

ListNode* make_list(vector<int> v) {
    ListNode* head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode* ptr = head;
        while (ptr->next) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

void inorder(TreeNode* root) {
    if (root) {
        inorder(root->left);
        cout << root->val << " ";
        inorder(root->right);
    }
}

class Solution {
public:
    pair<ListNode*, ListNode*> getMid(ListNode* a) {
        ListNode* prev = NULL;
        ListNode* fast = a;
        ListNode* slow = a;
        while (fast && fast->next) {
            fast = fast->next->next;
            prev = slow;
            slow = slow->next;
        }
        return {prev, slow};
    }

    TreeNode* sortedListToBST(ListNode* a) {
        if (!a) return NULL;
        auto x = getMid(a);
        ListNode* mid = x.second;
        TreeNode* node = new TreeNode(mid->val);
        ListNode* nextStart = mid->next;
        mid->next = NULL;
        node->right = sortedListToBST(nextStart);
        if (x.first) {
            x.first->next = NULL;
            node->left = sortedListToBST(a);
        }
        return node;
    }
};

int main() {
    vector<int> v = {-10,-3,0,5,9};
    ListNode* head = make_list(v);
    Solution ob;
    inorder(ob.sortedListToBST(head));
    return 0;
}

Đầu vào

[-10,-3,0,5,9]

Đầu ra

-10 -3 0 5 9