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 trong đó các phần tử được sắp xếp theo thứ tự tăng dần, chúng ta phải chuyển nó thành BST cân bằng chiều cao. Vì vậy, nếu danh sách có dạng [-10, -3, 0, 5, 9], Cây có thể sẽ giống như -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Nếu danh sách trống, sau đó trả về null

• Xác định một phương thức đệ quy được gọi là sortedListToBST (), điều này sẽ lấy nút bắt đầu danh sách

• x:=địa chỉ của nút trước của nút giữa từ danh sách a

• mid:=nút giữa chính xác

• tạo một nút mới với giá trị bằng cách lấy từ giá trị của giữa

• nextStart:=tiếp theo của nút giữa

• đặt giữa tiếp theo là null

• bên phải của nút:=sortedListToBST (nextStart)

• nếu x không phải là null, thì tiếp theo của x =null và bên trái của nút:=sortedListToBST (a)

• nút trả lại

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách 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;
   }
};
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