# Convert Sorted Array to Binary Search Tree

## Question

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

Given a sorted (increasing order) array,
Convert it to create a binary tree with minimal height.

Example
Given [1,2,3,4,5,6,7], return

4
/   \
2     6
/ \    / \
1   3  5   7
Note
There may exist multiple valid solutions, return any of them.


## 题解 - 折半取中

### C++

/**
* 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) {
if (num.empty()) {
return NULL;
}

return middleNode(num, 0, num.size() - 1);
}

private:
TreeNode *middleNode(vector<int> &num, const int start, const int end) {
if (start > end) {
return NULL;
}

TreeNode *root = new TreeNode(num[start + (end - start) / 2]);
root->left = middleNode(num, start, start + (end - start) / 2 - 1);
root->right = middleNode(num, start + (end - start) / 2 + 1, end);

return root;
}
};


### Java

/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/
public class Solution {
/**
* @param A: an integer array
* @return: a tree node
*/
public TreeNode sortedArrayToBST(int[] A) {
if (A == null || A.length == 0) return null;

return helper(A, 0, A.length - 1);
}

private TreeNode helper(int[] nums, int start, int end) {
if (start > end) return null;

int mid = start + (end - start) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, start, mid - 1);
root.right = helper(nums, mid + 1, end);

return root;
}
}