Function vectorToList prototype trick credit to:
http://stackoverflow.com/questions/13547273/c11-defining-function-on-stdarraychar-n
Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
#include <iostream>
#include <array>
using namespace std;
/**
* Definition for singly-linked list.*/
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
/**
* Definition for binary tree */
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* build(ListNode*& head, int start, int end){
//the head points to the first element initially
if (start > end) return NULL;
int mid = (start+end)/2;
TreeNode* leftChild = build(head, start, mid-1);
//assume the head will advance (mid-start) times
//after this above function returns, the head points to the middle element
TreeNode* root = new TreeNode(head->val);
root->left = leftChild;
head = head->next;//advance in the list
//now head points to the first element of the right half
root->right = build(head, mid+1, end);
//also, after this function returns, the head pointer
//advances (end-mid), and now points to the last element in the list
return root;
}
TreeNode *sortedListToBST(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode* it = head;
int size = 0;
while(it){
++size;
it = it->next;
}
return build(head, 0, size-1);
}
};
template<size_t N> ListNode* vectorToList(array<int, N> const& num){
if (!N) return NULL;
ListNode* head = new ListNode(num[0]);
ListNode* it = head;
for(size_t ii = 1; ii < N; ++ii, it = it->next){
it->next = new ListNode(num[ii]);
}//for ii
return head;
}
int main(){
array<int,3> a={3,5,8};
ListNode* head = vectorToList(a);
Solution s;
TreeNode* root = s.sortedListToBST(head);
cout<<"OK"<<endl;
}
Since the length of the list is needed only for counting the list-head advance steps, a slightly different version is derived:
class Solution {
public:
TreeNode* build(ListNode*& head, int size){
if (size<=0) return NULL;
int half = size/2;
TreeNode* leftChild = build(head, half);
//assume the head will advance (mid-start) times
//after this function returns, now the head points to the middle element
TreeNode* root = new TreeNode(head->val);
root->left = leftChild;
head = head->next;
root->right = build(head, size - half - 1);
//also, after this function returns, the head pointer
//advances (end-mid), and now points to the last element of the list
return root;
}
TreeNode *sortedListToBST(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode* it = head;
int size = 0;
while(it){
++size;
it = it->next;
}
return build(head, size);
}
};
