資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：將連結串列轉換為二叉搜尋樹
假設我們有一個單向連結串列，其中元素按非遞減順序排列，我們需要將其轉換為一個高度平衡的二叉搜尋樹。例如，如果列表為 [-10, -3, 0, 5, 9]，則可能的樹如下所示：
為了解決這個問題，我們將遵循以下步驟：
- 如果列表為空，則
- 返回 null
- 定義一個名為 sortedListToBST() 的遞迴方法，它將接收列表的起始節點作為輸入。
- x := 列表 a 中中間節點的前一個節點的地址
- mid := 確切的中間節點
- 建立一個新節點，其值取自 mid 的值。
- nextStart := 中間節點的下一個節點
- 將 mid 的 next 設定為 null。
- 節點的右子節點 := sortedListToBST(nextStart)
- 如果 x 不為空，則
- x 的 next = null，節點的左子節點 := sortedListToBST(a)
- 返回節點
讓我們看看下面的實現，以便更好地理解：
示例
#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));
}輸入
[-10,-3,0,5,9]
輸出
-10 -3 0 5 9
更新於: 2020-11-19
471 次瀏覽
廣告