LintCode-排序列表轉(zhuǎn)換為二分查找樹分析及實(shí)例
更新時(shí)間：2017年04月25日 10:34:10 投稿：lqh
這篇文章主要介紹了LintCode-排序列表轉(zhuǎn)換為二分查找樹分析及實(shí)例的相關(guān)資料,需要的朋友可以參考下
給出一個(gè)所有元素以升序排序的單鏈表，將它轉(zhuǎn)換成一棵高度平衡的二分查找樹
您在真實(shí)的面試中是否遇到過這個(gè)題？
分析：就是一個(gè)簡(jiǎn)單的遞歸，只是需要有些鏈表的操作而已
代碼：
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: a tree node
*/
TreeNode *sortedListToBST(ListNode *head) {
// write your code here
if(head==nullptr)
return nullptr;
int len = 0;
ListNode*temp = head;
while(temp){len++;temp = temp->next;};
if(len==1)
{
return new TreeNode(head->val);
}
else if(len==2)
{
TreeNode*root = new TreeNode(head->val);
root->right = new TreeNode(head->next->val);
return root;
}
else
{
len/=2;
temp = head;
int cnt = 0;
while(cnt<len)
{
temp = temp->next;
cnt++;
}
ListNode*pre = head;
while(pre->next!=temp)
pre = pre->next;
pre->next = nullptr;
TreeNode*root = new TreeNode(temp->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(temp->next);
return root;
}
}
};
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
您可能感興趣的文章:
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于C++中函數(shù)修飾符的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-02-02
C++使用extern實(shí)現(xiàn)源文件變量與類成員函數(shù)的巧妙共享
C++中使用extern關(guān)鍵字可實(shí)現(xiàn)在源文件之間共享變量與類成員函數(shù),通過聲明變量或類在頭文件中,再在一個(gè)源文件中定義,其他源文件通過extern引用,促使模塊化、可維護(hù)的代碼組織,這篇文章主要介紹了C++用extern實(shí)現(xiàn)源文件變量與類成員函數(shù)的巧妙共享,需要的朋友可以參考下2024-03-03
數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言鏈表的實(shí)現(xiàn)介紹
大家好，本篇文章主要講的是數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言鏈表的實(shí)現(xiàn)介紹，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下2021-12-12
這篇文章主要介紹了C語(yǔ)言中String的常用函數(shù)用法，對(duì)學(xué)習(xí)String的小伙伴有一定的參考價(jià)值，感興趣的小伙伴可以借鑒一下2023-03-03
C++利用PCL點(diǎn)云庫(kù)操作txt文件詳解
這篇文章主要為大家詳細(xì)介紹了C++如何利用PCL點(diǎn)云庫(kù)操作txt文件,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價(jià)值,感興趣的小伙伴可以了解一下2024-01-01
詳解Qt6?QML?Settings?location?不創(chuàng)建指定路徑文件
到Qt6以后,?棄用了fileName屬性,改用location屬性,但有個(gè)坑,本文就來介紹一下Qt6?QML?Settings?location不創(chuàng)建指定路徑文件,具有一定的參考價(jià)值,感興趣的可以了解一下2025-03-03
任何東西都可以認(rèn)為是異常，錯(cuò)誤只是異常的一種。本文將帶大家了解C++中異常是什么，是如何捕獲和處理的等相關(guān)知識(shí)。文中示例代碼簡(jiǎn)潔易懂，感興趣的小伙伴可以了解一下2022-08-08
詳解C++ 編寫String 的構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)
這篇文章主要介紹了詳解C++ 編寫String 的構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)的相關(guān)資料,這里提供實(shí)例幫助大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2017-08-08
C++ ffmpeg硬件解碼的實(shí)現(xiàn)方法
這篇文章主要介紹了C++ ffmpeg硬件解碼的實(shí)現(xiàn)，對(duì)FFmpeg多媒體解決方案中的視頻編解碼流程進(jìn)行研究。為嵌入式多媒體開發(fā)提供參考，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
這篇文章給大家介紹 stl vector用法，主要知識(shí)點(diǎn)在如何恰當(dāng)?shù)氖褂盟鼈兊某蓡T函數(shù)，涉及到條件函數(shù)和函數(shù)指針在迭代算法中的使用，對(duì)stl vector用法感興趣的朋友可以參考下本文2015-10-10