Задача: 109. Convert Sorted List to Binary Search Tree
Сложность: medium

Дана голова односвязного списка, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте бинарное дерево поиска.

Пример:

Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5]

👨‍💻 Алгоритм:

1⃣Так как список односвязный, для нахождения середины используем два указателя: slow_ptr (двигается на 1 узел) и fast_ptr (на 2 узла). Когда fast_ptr дойдёт до конца, slow_ptr будет в середине.

2⃣Для отделения левой части от средней сохраняем prev_ptr, который указывает на узел перед slow_ptr. Затем делаем prev_ptr->next = nullptr, чтобы отсоединить левую часть списка.

3⃣Рекурсивно строим левое поддерево из головы списка, правое — из mid->next. Базовый случай — если head == mid, это лист, возвращаем его как TreeNode.

😎 Решение:

class Solution {
public:
    ListNode* findMiddleElement(ListNode* head) {
        ListNode* prevPtr = nullptr;
        ListNode* slowPtr = head;
        ListNode* fastPtr = head;

        while (fastPtr != nullptr && fastPtr->next != nullptr) {
            prevPtr = slowPtr;
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }

        if (prevPtr != nullptr) {
            prevPtr->next = nullptr;
        }
        return slowPtr;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        ListNode* mid = this->findMiddleElement(head);
        TreeNode* node = new TreeNode(mid->val);

        if (head == mid) {
            return node;
        }

        node->left = this->sortedListToBST(head);
        node->right = this->sortedListToBST(mid->next);
        return node;
    }
};

Ставь 👍 и забирай 📚 Базу знаний