109. Convert Sorted List to Binary Search Tree

01//recursion
02//Runtime: 40 ms, faster than 46.56% of C++ online submissions for Convert Sorted List to Binary Search Tree.
03//Memory Usage: 36.1 MB, less than 5.43% of C++ online submissions for Convert Sorted List to Binary Search Tree.
04/**
05 * Definition for singly-linked list.
06 * struct ListNode {
07 *     int val;
08 *     ListNode *next;
09 *     ListNode() : val(0), next(nullptr) {}
10 *     ListNode(int x) : val(x), next(nullptr) {}
11 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
12 * };
13 */
14/**
15 * Definition for a binary tree node.
16 * struct TreeNode {
17 *     int val;
18 *     TreeNode *left;
19 *     TreeNode *right;
20 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
21 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
22 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
23 * };
24 */
25class Solution {
26public:
27    TreeNode* sortedListToBST(ListNode* head) {
28        if(!head) return nullptr;
29        
30        ListNode* dummy = new ListNode(-1);
31        dummy->next = head;
32        
33        ListNode *slow = dummy, *fast = dummy;
34        ListNode *preslow;
35        
36        while(fast && fast->next){
37            preslow = slow;
38            slow = slow->next;
39            fast = fast->next->next;
40        }
41        
42        cout << preslow->val << ", " << slow->val << endl;
43        
44        //now slow is the midpoint(for odd-length list) or 
45        // the node before midpoint(for even-length list)
46        //preslow is the previous node of slow
47        
48        TreeNode* root = new TreeNode(slow->val);
49        
50        //cut the list's former part with the processed "slow"
51        preslow->next = nullptr;
52        //when slow==head, this node doesn't have left subtree
53        root->left = (slow == head) ? nullptr : sortedListToBST(head);
54        
55        root->right = sortedListToBST(slow->next);
56        
57        return root;
58    }
59};
60
61//recursion, without dummy
62//Runtime: 40 ms, faster than 46.56% of C++ online submissions for Convert Sorted List to Binary Search Tree.
63//Memory Usage: 32.9 MB, less than 5.43% of C++ online submissions for Convert Sorted List to Binary Search Tree.
64//time: O(NlogN)
65//in ith recursion(i starts from 1), we use (N/pow(2,i)) times to find middle point, do it pow(2,i-1) times
66//and we will do that for logN recursions, so it sums up to NlogN/2, which is O(NlogN)
67//space: O(logN)
68//recursion space used by "balanced" tree
69class Solution {
70public:
71    TreeNode* sortedListToBST(ListNode* head) {
72        if(!head) return nullptr;
73        
74        ListNode *slow = head, *fast = head;
75        ListNode *preslow = nullptr;
76        
77        while(fast && fast->next){
78            preslow = slow;
79            slow = slow->next;
80            fast = fast->next->next;
81        }
82        
83        // cout << (preslow ? preslow->val : -1) << ", " << slow->val << endl;
84        
85        //now slow is the midpoint(for odd-length list) or 
86        // the node after midpoint(for even-length list)
87        //preslow is the previous node of slow
88        
89        TreeNode* root = new TreeNode(slow->val);
90        
91        //cut the list's former part with the processed "slow"
92        //if slow is head, it means the list's length is 1,
93        //and preslow is nullptr
94        if(slow == head){
95            return root;
96        }
97        
98        //if slow != head, it has left subtree
99        preslow->next = nullptr;
100        
101        root->left = sortedListToBST(head);
102        
103        root->right = sortedListToBST(slow->next);
104        
105        return root;
106    }
107};
108
109//Approach 2: Recursion + Conversion to Array
110//use more space to reduce time complexity
111//Runtime: 40 ms, faster than 46.56% of C++ online submissions for Convert Sorted List to Binary Search Tree.
112//Memory Usage: 33.4 MB, less than 5.43% of C++ online submissions for Convert Sorted List to Binary Search Tree.
113//time: O(N), space: O(N)
114class Solution {
115public:
116    TreeNode* sortedVectorToBST(vector<int>& arr, int start, int end){
117        if(start > end) return nullptr;
118        
119        int mid = (start+end)>>1;
120        TreeNode* root = new TreeNode(arr[mid]);
121        
122        root->left = sortedVectorToBST(arr, start, mid-1);
123        root->right = sortedVectorToBST(arr, mid+1, end);
124        
125        return root;
126    }
127    
128    TreeNode* sortedListToBST(ListNode* head) {
129        vector<int> arr;
130        
131        while(head){
132            arr.push_back(head->val);
133            head = head->next;
134        }
135        
136        int n = arr.size();
137        
138        return sortedVectorToBST(arr, 0, n-1);
139    }
140};
141
142//Approach 3: Inorder Simulation
143//Runtime: 40 ms, faster than 46.56% of C++ online submissions for Convert Sorted List to Binary Search Tree.
144//Memory Usage: 33.1 MB, less than 5.43% of C++ online submissions for Convert Sorted List to Binary Search Tree.
145//time: O(N), space: O(logN)
146class Solution {
147public:
148    ListNode* head;
149    
150    TreeNode* convertListToBST(int start, int end){
151        if(start > end){
152            // cout << "return nullptr" << endl;
153            return nullptr;
154        }
155        
156        int mid = (start+end) >> 1;
157        
158        TreeNode* left = convertListToBST(start, mid-1);
159        
160        // cout << start << ", " << end << ", " << this->head->val << endl;
161        TreeNode* root = new TreeNode(this->head->val);
162        root->left = left;
163        
164        this->head = this->head->next;
165        
166        root->right = convertListToBST(mid+1, end);
167        
168        // cout << "return " << root->val << endl;
169        return root;
170    }
171    
172    TreeNode* sortedListToBST(ListNode* head) {
173        if(!head) return nullptr;
174        
175        int n = 0;
176        
177        ListNode* cur = head;
178        
179        while(cur){
180            ++n;
181            cur = cur->next;
182        }
183        
184        this->head = head;
185        
186        return convertListToBST(0, n-1);
187    }
188};