Accepted C++ solution w/o constructing new vectors
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 solutio
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.\n\n\n    class Solution {\n        TreeNode *dfs(vector<int> &num, int start, int end) {\n            int idx = start + (end-start)/2;\n            TreeNode *node = new TreeNode(num[idx]);\n            \n            //Base case\n            if(end == start) \n                return node;  \n                \n            //recurse if valid\n            if(start <= idx-1)\n                node->left = dfs(num, start, idx-1);\n            if(idx+1 <= end)\n                node->right = dfs(num, idx+1, end);\n            \n            return node;\n        }\n    public:\n        TreeNode *sortedArrayToBST(vector<int> &num) {\n            if(num.empty()) return nullptr;    //check empty case\n            \n            return dfs(num, 0, num.size()-1);\n        }\n    };
[]