Convert Sorted Array to Binary Search Tree

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

简单的深搜问题。

每次取mid=(start + end) / 2;

然后以num[mid]为root，深搜root->left, 和root->right。

复杂度o(n)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        return DFS(num, 0, num.size());
    }
    //[start, end)
    TreeNode *DFS(vector<int> &num, int start, int end){
        int mid = (start + end) / 2;
        if(start >= end) return NULL;
        TreeNode * thisNode = new TreeNode(num[mid]);
        thisNode->left = DFS(num, start, mid);
        thisNode->right = DFS(num, mid + 1, end);
        return thisNode;
    }
};