LintCode如何實現(xiàn)排序列表轉(zhuǎn)換為二分查找樹

這篇文章給大家分享的是有關(guān)LintCode如何實現(xiàn)排序列表轉(zhuǎn)換為二分查找樹的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

給出一個所有元素以升序排序的單鏈表，將它轉(zhuǎ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; 
    
  } 
 } 
};

感謝各位的閱讀！關(guān)于“LintCode如何實現(xiàn)排序列表轉(zhuǎn)換為二分查找樹”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！