leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0109.cpp (1108B)

0 class Solution { 1 struct record { 2 TreeNode *root; 3 ListNode *low, *high; 4 record(TreeNode *root, ListNode *low = nullptr, ListNode *high = nullptr) 5 : root(root), low(low), high(high) {} 6 }; 7 ListNode *get_mid(ListNode *list, ListNode *end) { 8 ListNode *slow, *fast; 9 slow = fast = list; 10 while (fast != end && fast->next != end) { 11 fast = fast->next->next; 12 slow = slow->next; 13 } 14 return slow; 15 } 16 17 public: 18 TreeNode *sortedListToBST(ListNode *head) { 19 stack<record> st; 20 TreeNode *tree = new TreeNode(INT_MIN), *t; 21 st.push({tree, head, nullptr}); 22 while (!st.empty()) { 23 record r = st.top(); 24 st.pop(); 25 while (r.low != r.high) { 26 ListNode *mid = get_mid(r.low, r.high); 27 (mid->val >= r.root->val ? r.root->right : r.root->left) = t = new TreeNode(mid->val); 28 st.push({r.root = t, mid->next, r.high}); 29 r.high = mid; 30 } 31 } 32 return tree->right; 33 } 34 };