177. Convert Sorted Array to Binary Search Tree With Minimal Height
Given a sorted (increasing order) array, Convert it to create a binary tree with minimal height.
Example
Example 1:
Input: {1,2}
Output: A binary search tree with minimal height.
Explanation:
2
/
1
Example 2:
Input: {1,2,3,4,5,6,7}
Output: A binary search tree with minimal height.
Explanation:
4
/ \
2 6
/ \ / \
1 3 5 7
Notice
There may exist multiple valid solutions, return any of them.
思路：
Binary Search Tree特性：Binary Search Tree中序遍历的结果是升序数组。对于一个升序数组，一旦确定了根节点，根节点左半边部分全部属于左子树，根节点右半部分全部属于右子树。
最小高度的二叉树，就要尽可能满足其平衡。也就是说尽量保证根节点的左子树和右子树的节点个数差不多。所以一开始把数组中间的那个数定为根节点。
一旦确定了根节点在数组中的index值，其左子树的范围则是A[start, index - 1]，右子树的范围则是A[index + 1, end], 然后用分治法递归，求出根的左子树和右子树
代码：
/**
* 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.length == 0 || A == null) {
return null;
}
return helper(A, 0, A.length - 1);
}
public TreeNode helper(int[] A, int start, int end) {
if (start > end) {
return null;
}
if (start == end) {
return new TreeNode(A[start]);
}
int mid = (start + end) / 2;
TreeNode root = new TreeNode(A[mid]);
root.left = helper(A, start, mid - 1);
root.right = helper(A, mid + 1, end);
return root;
}
}