LintCode-排序列表转换为二分查找树分析及实例

给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树

您在真实的面试中是否遇到过这个题？ 

分析：就是一个简单的递归，只是需要有些链表的操作而已

代码：

 
class Solution { 
public: 
  
 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(cntnext; 
    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; 
    
  } 
 } 
}; 

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！