Accepted C++ solution w/o constructing new vectors

  • 6

    As far as I know, construction of "subvectors" could be expensive ( O(n) operation). So I tried to avoid creating new vectors for performance. Here's my solution.

    class Solution {
        TreeNode *dfs(vector<int> &num, int start, int end) {
            int idx = start + (end-start)/2;
            TreeNode *node = new TreeNode(num[idx]);
            //Base case
            if(end == start) 
                return node;  
            //recurse if valid
            if(start <= idx-1)
                node->left = dfs(num, start, idx-1);
            if(idx+1 <= end)
                node->right = dfs(num, idx+1, end);
            return node;
        TreeNode *sortedArrayToBST(vector<int> &num) {
            if(num.empty()) return nullptr;    //check empty case
            return dfs(num, 0, num.size()-1);

  • 0

    why do you use int idx = start + (end-start)/2; instead of (start + end) / 2

  • 0

    avoid potential integer overflow

  • 0

    maybe you could use a vector pointer as global variable and make it point to the vector num.

  • 0

    I believe that is the same as passing a reference to a vector

Log in to reply

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