LintCode-排序列表轉換為二分查找樹分析及實例

LintCode-排序列表轉換為二分查找樹分析及實例。本站提示廣大學習愛好者：（LintCode-排序列表轉換為二分查找樹分析及實例）文章只能為提供參考，不一定能成為您想要的結果。以下是LintCode-排序列表轉換為二分查找樹分析及實例正文

給出一個所有元素以升序排序的單鏈表，將它轉換成一棵高度平衡的二分查找樹

您在真實的面試中是否遇到過這個題？ 

分析：就是一個簡單的遞歸，只是需要有些鏈表的操作而已

代碼：

/** 
 * 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; 
    
  } 
 } 
}; 

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！