Convert Sorted Array to Balanced Binary Search Tree

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

http://www.lintcode.com/en/problem/convert-sorted-array-to-binary-search-tree-with-minimal-height/

Solution

借鉴binary search的思想。O(n) runtime, O(log n) stack space – Divide and conquer。

class Solution {
public:
    /**
     * @param A: A sorted (increasing order) array
     * @return: A tree node
     */
    TreeNode *sortedArrayToBST(vector<int> &A) {
        // write your code here
        TreeNode *root = NULL;
        if (A.size() == 0)
            return root;
        root = bst(A, 0, A.size()-1);
    }
private:
    TreeNode *bst(vector<int> &A, int start, int end) {
        if(start == end) {
            return (new TreeNode(A[start]));
        } 
        if(start > end) return NULL; //刚开始是忘记了这句，那当start>end的时候就退出不了了。
        int mid = start+(end-start)/2;
        TreeNode *root = new TreeNode(A[mid]);
       // int tmp = mid-1<start ? start : mid-1;//新的end是可能小于start的，见上句。
        int tmp = mid-1;
        root->left = bst(A, start, tmp); 
        //tmp = mid+1 > end ? end : mid+1;
        tmp = mid+1;
        root->right = bst(A, tmp, end);
        return root;

    }
};

以上是自顶向下的构建BST，也可以自底向上的构建。

TreeNode *helper(vector<int> &A, int start, int end) {
        if(start > end) return NULL;
        if(start == end) return new TreeNode(A[start]);
        int mid = start + (end - start) /2;

        TreeNode *left = helper(A, start, mid-1); //find left child in the left part the A
        TreeNode *root = new TreeNode(A[mid]);
        root->left = left;
        root->right = helper(A, mid+1, end);
        return root;
    }