Chuyển Đổi Danh Sách Đã Sắp Xếp Thành Cây Tìm Kiếm Nhị Phân Trong C++

Giả sử chúng ta có một danh sách liên kết đơn nơi các phần tử được sắp xếp theo thứ tự tăng dần, chúng ta phải chuyển đổi nó thành một cây BST cân bằng chiều cao. Ví dụ: danh sách [-10, -3, 0, 5, 9] → cây BST như hình.

Để giải quyết, chúng ta làm theo các bước:

• Nếu danh sách rỗng, trả về null.

• Định nghĩa phương thức đệ quy sortedListToBST() nhận nút đầu danh sách.

• Tìm nút giữa (mid) và nút trước nó (prev) bằng con trỏ nhanh/chậm.

• Tạo nút cây mới với giá trị mid.

• nextStart := next của mid; đặt mid->next = null.

• Cây con phải := sortedListToBST(nextStart).

• Nếu prev không null: prev->next = null; cây con trái := sortedListToBST(head).

• Trả về nút gốc.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#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 != NULL){
            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 inord(TreeNode *root){
    if(root != NULL){
        inord(root->left);
        cout << root->val << " ";
        inord(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;
        pair<ListNode*, ListNode*> 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;
    inord(ob.sortedListToBST(head));
}

Đầu vào

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

Đầu ra

-10 -3 0 5 9