Convert Sorted List to Binary Search Tree

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 /**
10  * Definition for binary tree
11  * struct TreeNode {
12  *     int val;
13  *     TreeNode *left;
14  *     TreeNode *right;
15  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
16  * };
17  */
18 class Solution {
19 public:
20     TreeNode *sortedListToBST(ListNode *head) {
21         return sortedListToBSTRe(head, getLength(head));
22     }
23     
24     TreeNode* sortedListToBSTRe(ListNode* &head, int length)
25     {
26         if(length == 0) return NULL;
27         int mid = length / 2;
28         TreeNode* left = sortedListToBSTRe(head, mid);
29         TreeNode* root = new TreeNode(head->val);
30         TreeNode* right = sortedListToBSTRe(head->next, length - mid - 1);
31         root->left = left;
32         root->right = right;
33         head = head->next;
34         return root;
35     }
36     
37     int getLength(ListNode* head) 
38     {
39         int length = 0;
40         while(head) {
41             length++;
42             head = head->next;
43         }
44         return length;
45     }
46 };