和我一起在LeetCode刷题吧（每天一题LeetCode）

分类标签：链表               

难易度：中等

题目描述：

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0

    / \

  -3  9

  /  /

-10  5

思路：转换成数组+二分法+递归

1.利用空间使用更多的空间来降低时间的复杂度；

2.在递归过程中对链表的制作处理会比较繁琐，将链表转换成数组，并将该链表构成的数组的头和尾分别命名为left和right；

3.利用二分法寻找二叉树搜索树的根节点

代码：

struct TreeNode *numTranslate(int *num,int left,int right)

{

    if(left>right)

        return NULL;

    int mid=(left+right)/2;

    struct TreeNode * res=(struct TreeNode *)malloc(sizeof(struct TreeNode));

    res->val=num[mid];

    res->left=numTranslate(num,left,mid-1);

    res->right=numTranslate(num,mid+1,right);

    return res;

}

struct TreeNode* sortedListToBST(struct ListNode* head){

struct ListNode *cur=head;

    int count=0,k=0;

    while(cur!=NULL)

    {

        count++;

        cur=cur->next;

    }

    cur=head;

  int * num=(int *)calloc(sizeof(int),count);

    while(cur!=NULL)

    {

      num[k++]=cur->val;

        cur=cur->next;

    }

return numTranslate(num,0,count-1);

}

运行结果：

程序生成的二叉树 程序损耗的时间和空间