Super simple O(n) time C++ solution


  • 1
    X
    class Solution {
    private:
        TreeNode* sortToBSTInner(vector<int>&num, int front, int back) {
            if(front>back) return NULL;
            int mid = front + (back-front)/2;
            TreeNode* left = sortToBSTInner(num, front, mid-1);
            TreeNode* current = new TreeNode(num[mid]);
            current->left = left;
            current->right = sortToBSTInner(num, mid+1, back);
            return current;
        }
    public:
        TreeNode *sortedArrayToBST(vector<int> &num) {
            if(num.empty()) return NULL;
            return sortToBSTInner(num, 0, num.size()-1);
        }
    };

  • 0
    C

    I have the same algorithm with you. But for left branch, I think it could be involved in the current->left. Here is my code:

    TreeNode* create(const vector<int> &num, int start,int end){
            if(start>end) return NULL;
            int mid = (start+end)/2;
            TreeNode *root = new TreeNode(num[mid]);
            if(start == end) return root;
            root->left = create(num,start,mid-1);
            root->right = create(num,mid+1,end);
        }
        TreeNode *sortedArrayToBST(vector<int> &num) {
            if(num.empty()) return NULL;
            return create(num,0,num.size()-1);
        }

Log in to reply
 

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