LeetCode – Refresh – 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 *getTree(ListNode **head, int start, int end) {
21         if (start > end) return NULL;
22         int mid = (start + end)/2;
23         TreeNode *lnode = getTree(head, start, mid-1);
24         TreeNode *root = new TreeNode((*head)->val);
25         *head = (*head)->next;
26         root->left = lnode;
27         root->right = getTree(head, mid+1, end);
28         return root;
29     }
30     TreeNode *sortedListToBST(ListNode *head) {
31         if (!head) return NULL;
32         ListNode *runner = head;
33         int index = 0;
34         while (runner->next) {
35             runner = runner->next;
36             index++;
37         }
38         return getTree(&head, 0, index);
39     }
40 };