Short C++ recursion


  • 0
        TreeNode* sortedListToBST(ListNode* head) {
            return dfs(head, nullptr);
        }
        
        TreeNode* dfs(ListNode* h, ListNode* t) {
            if (h == t) return nullptr;
            auto mid = getMid(h, t);
            auto r = new TreeNode(mid->val);
            r->left = dfs(h, mid), r->right = dfs(mid->next, t);
            return r;
        }
        
        ListNode* getMid(ListNode* h, ListNode* t) {
            auto slow = h, fast = h;
            while (fast->next and 
                   fast->next->next and 
                   fast->next != t and 
                   fast->next->next != t) 
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.