Sunday, April 21, 2013

Leetcode: Convert Sorted Array to Binary Search Tree in C++

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

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

No comments:

Post a Comment