clean and easy to understand c++ solutioin


  • 1
    D
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if (!head) return nullptr;
            if (!head -> next) return new TreeNode(head -> val);
            
            ListNode *pre = findMid(head), *mid = pre -> next, *after = mid -> next;
            pre -> next = nullptr;  // break linked list into 2
            
            TreeNode *root = new TreeNode(mid -> val);
            root -> left = sortedListToBST(head);
            root -> right = sortedListToBST(after);
            return root;
        }
        
        ListNode *findMid(ListNode *head) {
            ListNode *slow = head, *pre = nullptr;
            while (head && head -> next) {
                pre = slow;
                slow = slow -> next;
                head = head -> next -> next;
            }
            return pre;
        }
    };
    

Log in to reply
 

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