O(n) space concise, easy understanding C++ solution


  • 0
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            vector<ListNode*> temp;
            while (head) {
                temp.push_back(head);
                head = head->next;
            }
            return helper(temp, 0, temp.size() - 1);
        }
        
        TreeNode* helper(vector<ListNode*>& temp, int l, int r) {
            if (l > r) return NULL;
            else {
                int m = l + (r - l) / 2;
                TreeNode* root = new TreeNode(temp[m]->val);
                root->left = helper(temp, l, m - 1);
                root->right = helper(temp, m + 1, r);
                return root;
            }
        }
    };
    

Log in to reply
 

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