LeetCode刷题笔记-递归-将有序数组转换为二叉搜索树
题目描述
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/
-3 9
/ /
-10 5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
解题思路：
1、 根节点root=nums[mid]
2、root.left=左边剩余部分的中间值
3、root.right=左边剩余部分的中间值
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 class Solution { 11 public TreeNode sortedArrayToBST(int[] nums) { 12 if(nums.length==0) return null; 13 else{ 14 return digui(nums,0,nums.length-1); 15 } 16 } 17 18 public TreeNode digui(int[] nums,int left,int right){ 19 if(left>right){ 20 return null; 21 } 22 23 int mid=left+(right-left)/2; //避免溢出风险；；；； 24 TreeNode root = new TreeNode(nums[mid]); 25 root.left=digui(nums,left,mid-1); 26 root.right=digui(nums,mid+1,right); 27 return root; 28 } 29 }