Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
代码语言：javascript复制Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/
-3 9
/ /
-10 5
用c 的指针写，还是比较烦的‘
c class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if(head==NULL) return NULL;
int l = 0 ;
int r = 0 ;
ListNode* term = head;
ListNode* left2 = NULL;
ListNode* right2 = NULL;
ListNode* left;
ListNode* right;
while(term!=NULL)
{
r ;
term = term->next;
}
int mid =(l r)/2;
term = head;
int value;
l=0;
while(term!=NULL)
{
if(l<mid)
{
ListNode* temp = new ListNode(term->val);
if(left2 == NULL) {left2 = temp;left = left2;}
else{
left->next = temp;
left = left->next;
}
}
else if(l>mid)
{
ListNode* temp = new ListNode(term->val);
if(right2 == NULL) {right2 = temp;right=right2;}
else{
right->next = temp;
right = right->next;
}
}
else if(l==mid)
value = term->val;
term = term->next;
l ;
}
TreeNode* tree = new TreeNode(value);
tree->left = sortedListToBST(left2);
tree->right = sortedListToBST(right2);
return tree;
}
};
