leetCode 108.Convert Sorted Array to Binary Search Tree(将排序数组转换为BST) 答题思路和方法

leetCode 108.Convert Sorted Array to Binary Search Tree(将排序数组转换为BST) 解题思路和方法

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

思路：将排序数组转换为高度平衡的二叉搜索树。思想是将中间的值作为根节点，然后左右的数组分别为左右子树。递归求解。

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
	public TreeNode sortedArrayToBST(int[] nums) {
        /**
         * 高度平衡二叉搜索树
         * 指左右子树的高度差不超过1
         * 所以每次从中间构造根节点
         * 两边构造左右子树
         */ 
        return BST(nums,0,nums.length-1);
    }
	
	private TreeNode BST(int[] nums, int i, int j){
		if(i > j){
			return null;
		}
		int mid = (j + i + 1)/2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = BST(nums,i,mid-1);
        root.right = BST(nums,mid+1,j);
        return root;
	}
}