Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
What is a BST：
若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树。
What is height-balanced:
An empty tree is height-balanced. A non-empty binary tree T is balanced if: 1) Left subtree of T is balanced 2) Right subtree of T is balanced 3) The difference between heights of left subtree and right subtree is not more than 1.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0){
return null;
}
return helper(nums, 0, nums.length - 1);
}
private TreeNode helper(int[] nums, int left, int right){
if (left > right){
return null;
}
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = helper(nums, left, mid - 1);
node.right = helper(nums, mid + 1, right);
return node;
}
}
