当前位置: 首页 > 编程笔记 >

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

奚卓
2023-03-14
本文向大家介绍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; 
    
  } 
 } 
}; 

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

 类似资料:
  • 主要内容:什么是二叉排序树?,使用二叉排序树查找关键字,二叉排序树中插入关键字,二叉排序树中删除关键字,总结前几节介绍的都是有关静态 查找表的相关知识,从本节开始介绍另外一种查找表—— 动态查找表。 动态查找表中做查找操作时,若查找成功可以对其进行删除;如果查找失败,即表中无该关键字,可以将该关键字插入到表中。 动态查找表的表示方式有多种,本节介绍一种使用树结构表示动态查找表的实现方法—— 二叉排序树(又称为 “二叉查找树”)。 什么是二叉排序树? 二叉排序树要么是空 二叉树,要么具有如下特点:

  • 随着二叉搜索树的实现完成,我们将对已经实现的方法进行快速分析。让我们先来看看 put 方法。其性能的限制因素是二叉树的高度。从词汇部分回忆一下树的高度是根和最深叶节点之间的边的数量。高度是限制因素,因为当我们寻找合适的位置将一个节点插入到树中时,我们需要在树的每个级别最多进行一次比较。 二叉树的高度可能是多少?这个问题的答案取决于如何将键添加到树。如果按照随机顺序添加键,树的高度将在 $$log2

  • 本文向大家介绍C#二分查找算法实例分析,包括了C#二分查找算法实例分析的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了C#二分查找算法。分享给大家供大家参考。具体实现方法如下: 希望本文所述对大家的C#程序设计有所帮助。

  • Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its in

  • 本文向大家介绍PHP折半(二分)查找算法实例分析,包括了PHP折半(二分)查找算法实例分析的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了PHP折半(二分)查找算法。分享给大家供大家参考,具体如下: 折半查询只适用于已经按照正序或者逆序排序的数组,字符串等; 算法: 先取数组的中间位置,无中间位置,则向下取整; 从中间进行折半,大小判断,进入前半段或者后半段; 再对前半段或者后半段进行同样

  • 本文向大家介绍python 二分查找和快速排序实例详解,包括了python 二分查找和快速排序实例详解的使用技巧和注意事项,需要的朋友参考一下 思想简单,细节颇多;本以为很简单的两个小程序,写起来发现bug频出,留此纪念。 总结 以上所述是小编给大家介绍的python 二分查找和快速排序实例详解,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对呐喊教程网