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ì)長(zhǎng)度比較麻煩摘仅，先轉(zhuǎn)化為數(shù)組即可。
也可以使用一個(gè)指針走一步囚玫，另一個(gè)指針走兩步來獲得中間的結(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);
}
