Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

分析

將鏈表轉(zhuǎn)化為平衡的二叉排序樹，可以用上一題的思路，將中間的點(diǎn)作為根節(jié)點(diǎn)，左邊的為左子樹，右邊的為右子樹。依次遞歸即可。由于鏈表統(tǒng)計(jì)長度比較麻煩，先轉(zhuǎn)化為數(shù)組即可。
也可以使用一個指針走一步，另一個指針走兩步來獲得中間的結(jié)點(diǎn)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* convert(int* nums,int numsSize,int left,int right)
{
    if(left<=right)
    {
        struct TreeNode *rootNode=(struct TreeNode *)malloc(sizeof(struct TreeNode ));
        rootNode->val=nums[(left+right)/2];
        rootNode->left=convert(nums,numsSize,left,(left+right)/2-1);
        rootNode->right=convert(nums,numsSize,(left+right)/2+1,right);
        return rootNode;
    }
    return NULL;
}
int nums[100000];
struct TreeNode* sortedListToBST(struct ListNode* head) {
    int numsSize=0;
    struct ListNode *temp=head;
    while(temp!=NULL)
    {
        nums[numsSize]=temp->val;
        temp=temp->next;
        numsSize++;
    }
    if(numsSize==0)return NULL;
    else
        return convert(nums,numsSize,0,numsSize-1);
}