package mrzhang.leecode;

/**
 * @author zhangnianlei
 * @date 2020/7/7
 * 108. 将有序数组转换为二叉搜索树
 */
public class Solution108 {

	
	public static TreeNode sortedArrayToBST(int[] nums) {
		return dfs(nums, 0, nums.length - 1);
	}

	/**
	 * @description 递归的构建一棵二叉搜索树
	 * @author zhangnianlei
	 * @date 2020/7/11
	 * @exception
	 * @param: nums
	 * @param: left
	 * @param: right
	 * @return: mrzhang.leecode.TreeNode
	 * @modifier
	 */
	private static TreeNode dfs(int[] nums, int left, int right) {
		if (left > right) {
			return null;
		}
		int mid = left + (right - left) / 2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = dfs(nums, left, mid - 1);
		root.right = dfs(nums, mid + 1, right);
		return root;
	}


	/**
	 * @description 编写一个main函数在本地检验
	 * @author zhangnianlei
	 * @date 2020/7/11
	 * @exception
	 * @param: args
	 * @modifier
	 */
	public static void main(String[] args) {
		int[] nums = {-10,-3,0,5,9};
		TreeNode root = sortedArrayToBST(nums);
		TreeNode.prePrint(root);
	}

}