Convert Sorted Array to Binary Search Tree

LeetCode #108

Description:

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

Example:

Note

Idea:

sorted array in ascending order, is just the inorder traversal of BST.

So first find the root (should be the middle of the array), then recursively construct the left subtree (begin of array to mid) and right subtree (mid of array to end).

构建的过程相当于preorder.

Code:

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums.begin(), nums.end());
    }

    template<typename T>
    TreeNode* sortedArrayToBST(T it_begin, T it_end){
        if(it_begin==it_end) return NULL;

        auto it_mid=it_begin+(it_end-it_begin)/2;
        TreeNode * root = new TreeNode(*it_mid);
        root->left=sortedArrayToBST(it_begin, it_mid);
        root->right=sortedArrayToBST(next(it_mid), it_end);
        return root;
    }
};