您好,登錄后才能下訂單哦!
這篇文章主要講解了“C++怎么將有序鏈表轉(zhuǎn)為二叉搜索樹”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“C++怎么將有序鏈表轉(zhuǎn)為二叉搜索樹”吧!
Example:
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/
-3 9
/ /
-10 5
這道題是要求把有序鏈表轉(zhuǎn)為二叉搜索樹,和之前那道 Convert Sorted Array to Binary Search Tree 思路完全一樣,只不過是操作的數(shù)據(jù)類型有所差別,一個(gè)是數(shù)組,一個(gè)是鏈表。數(shù)組方便就方便在可以通過index直接訪問任意一個(gè)元素,而鏈表不行。由于二分查找法每次需要找到中點(diǎn),而鏈表的查找中間點(diǎn)可以通過快慢指針來操作,可參見之前的兩篇博客 Reorder List 和 Linked List Cycle II 有關(guān)快慢指針的應(yīng)用。找到中點(diǎn)后,要以中點(diǎn)的值建立一個(gè)數(shù)的根節(jié)點(diǎn),然后需要把原鏈表斷開,分為前后兩個(gè)鏈表,都不能包含原中節(jié)點(diǎn),然后再分別對(duì)這兩個(gè)鏈表遞歸調(diào)用原函數(shù),分別連上左右子節(jié)點(diǎn)即可。代碼如下:
解法一:
class Solution { public: TreeNode *sortedListToBST(ListNode* head) { if (!head) return NULL; if (!head->next) return new TreeNode(head->val); ListNode *slow = head, *fast = head, *last = slow; while (fast->next && fast->next->next) { last = slow; slow = slow->next; fast = fast->next->next; } fast = slow->next; last->next = NULL; TreeNode *cur = new TreeNode(slow->val); if (head != slow) cur->left = sortedListToBST(head); cur->right = sortedListToBST(fast); return cur; } };
我們也可以采用如下的遞歸方法,重寫一個(gè)遞歸函數(shù),有兩個(gè)輸入?yún)?shù),子鏈表的起點(diǎn)和終點(diǎn),因?yàn)橹懒诉@兩個(gè)點(diǎn),鏈表的范圍就可以確定了,而直接將中間部分轉(zhuǎn)換為二叉搜索樹即可,遞歸函數(shù)中的內(nèi)容跟上面解法中的極其相似,參見代碼如下:
解法二:
class Solution { public: TreeNode* sortedListToBST(ListNode* head) { if (!head) return NULL; return helper(head, NULL); } TreeNode* helper(ListNode* head, ListNode* tail) { if (head == tail) return NULL; ListNode *slow = head, *fast = head; while (fast != tail && fast->next != tail) { slow = slow->next; fast = fast->next->next; } TreeNode *cur = new TreeNode(slow->val); cur->left = helper(head, slow); cur->right = helper(slow->next, tail); return cur; } };
感謝各位的閱讀,以上就是“C++怎么將有序鏈表轉(zhuǎn)為二叉搜索樹”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對(duì)C++怎么將有序鏈表轉(zhuǎn)為二叉搜索樹這一問題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。