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; 

  }
 }
};

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

赞 (0)

相关推荐

  • LintCode 堆化详解及实例代码

    LintCode 堆化详解及实例代码 给出一个整数数组,堆化操作就是把它变成一个最小堆数组. 对于堆数组A,A[0]是堆的根,并对于每个A[i],A [i * 2 + 1]是A[i]的左儿子并且A[i * 2 + 2]是A[i]的右儿子. 样例 给出 [3,2,1,4,5],返回[1,2,3,4,5] 或者任何一个合法的堆数组 挑战 O(n)的时间复杂度完成堆化 说明 什么是堆? 堆是一种数据结构,它通常有三种方法:push, pop 和 top.其中,"push"添加新的元素进入堆,

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

    给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树 您在真实的面试中是否遇到过这个题? 分析:就是一个简单的递归,只是需要有些链表的操作而已 代码: /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } * Defin

  • Java实现二分查找树及其相关操作

    二分查找树(Binary Search Tree)的基本操作有搜索.求最大值.求最小值.求前驱.求后继.插入及删除. 对二分查找树的进行基本操作所花费的时间与树的高度成比例.例如有n个节点的完全二叉树,对它进行的基本操作的时间复杂度为O(logn).然而,如果树是一个有n个节点的线性的链,则在这种情况下的时间复杂度为O(n). 1.什么是二分查找树 二分查找树是一种有组织的二叉树.我们可以通过链接节点表示这样一棵树.每个节点包含键(key),数据(data),左子节点(left),右子节点(ri

  • java数据结构之二分查找法 binarySearch的实例

    java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.

  • C语言编程中实现二分查找的简单入门实例

    架设有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素.数组中有个元素 x,如何知道 x 位于该数组的第几位呢? 解决这个问题的一个普遍方法就是二分查找法.下面是程序: #include <stdio.h> int binsearch(int x, int v[], int n); main() { int i, result, n; int wait; int x = 17; // 需要查找的数值 int v[19]; // 定义一个数组 // 给数组赋值 for(i = 0;

  • Java二分查找算法实现代码实例

    这篇文章主要介绍了Java二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 二分查找: 两种方式: 非递归方式和递归方式 主要思路: 对于已排序的数组(先假定是从小到大排序), 先定义两个"指针", 一个"指向"首元素low, 一个"指向"末尾元素high. 然后, 开始折半比较, 即让要查找的数与数组中间的元素(索引为 low+high/2)比较. 若要查找的数比中间数小

  • C++二分查找(折半查找)算法实例详解

    本文实例讲述了C++二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难. 因此,折半查找方法适用于不经常变动而查找频繁的有序列表. 二分查找思想 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功: 否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 重复

  • 详解C语言中二分查找的运用技巧

    详解C语言中二分查找的运用技巧

    目录 基础的二分查 查找左侧边界 查找右侧边界 二分查找问题分析 实例1: 爱吃香蕉的珂珂 实例2:运送包裹 前篇文章聊到了二分查找的基础以及细节的处理问题,主要介绍了 查找和目标值相等的元素.查找第一个和目标值相等的元素.查找最后一个和目标值相等的元素 三种情况. 这些情况都适用于有序数组中查找指定元素 这个基本的场景,但实际应用中可能不会这么直接,甚至看了题目之后,都不会想到可以用二分查找算法来解决 . 本文就来分析下二分查找在实际中的应用,通过分析几个应用二分查找的实例,总结下能使用二分查

  • Python 二分查找之bisect库的使用详解

    目录 简介 bisect 库的使用 bisect_left bisect_right insort_left insort_right 二分查找基础实现 简介 bisect 库是 Python 标准库中的一部分,它提供了二分查找的功能.二分查找是一种在有序列表中查找某一特定元素的搜索算法.它的时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn),比顺序查找的时间复杂度 O ( n ) O(n) O(n) 要有效率. bisect 库的使用 bisect 库提供了 bise

  • Python判断列表是否已排序的各种方法及其性能分析

    声明 本文基于Python2.7语言,给出判断列表是否已排序的多种方法,并在作者的Windows XP主机(Pentium G630 2.7GHz主频2GB内存)上对比和分析其性能表现. 一. 问题提出 Haskell培训老师提出一个问题:如何判断列表是否已经排序? 排序与否实际只是相邻元素间的某种二元关系,即a->a->Bool.所以第一步可以把二元组列表找出来:第二步是把这个函数作用于每个元组,然后用and操作.老师给出的实现代码如下: pair lst = zip lst ( tail

  • C语言数据结构中二分查找递归非递归实现并分析

    C语言数据结构中二分查找递归非递归实现并分析

    C语言数据结构中二分查找递归非递归实现并分析 前言: 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高.因此较为受我们追捧.其实二分查找算法,是一个很经典的算法.但是呢,又容易写错.因为总是考虑不全边界问题. 用非递归简单分析一下,在编写过程中,如果编写的是以下的代码: #include<iostream> #include<assert.h> using namespace std; int binaty_search(int* arr, size_t n, int x)

随机推荐