leetcode

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 };