Accepted C++ solution w/o constructing new vectors


  • 6
    F

    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;
        }
    public:
        TreeNode *sortedArrayToBST(vector<int> &num) {
            if(num.empty()) return nullptr;    //check empty case
            
            return dfs(num, 0, num.size()-1);
        }
    };

  • 0
    R

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


  • 0
    B

    avoid potential integer overflow


  • 0
    E

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


  • 0
    F

    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.