Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Subscribe to see which companies asked this question
简单的说就是题目给出一个排好序的而且是升序的链表，我们需要将其转化为二叉排序树，根据二叉排序树定义，我们要每次找到这个链表的中点，并把其作为根，其左右边的进行递归，即可获得。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
vector
public:
TreeNode* sortedListToBST(ListNode* head) {
ListNode *temp = head;
while(temp !=NULL)
{
sum.push_back(temp->val);
temp = temp->next;
}
if( sum.size()== 0)
return NULL;
return build(0,sum.size()-1);
}
TreeNode* build(int start,int end)
{
TreeNode * root = (TreeNode *)malloc(sizeof(TreeNode));
int mid = (start+end)/2;
root->val = sum[mid];
if(mid == start)
root->left = NULL;
else
root->left = build(start,mid-1);
if(mid==end)
root->right = NULL;
else
root->right = build(mid+1,end);
return root;
}
};