108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹【簡單】

題目描述：

給你一個整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列，請你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹。

高度平衡 二叉樹是一棵滿足「每個節(jié)點(diǎn)的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。

示例 1：

輸入：nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：

示例 2：

輸入：nums = [1,3]
輸出：[3,1]
解釋：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索樹。

提示

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 按 嚴(yán)格遞增 順序排列

JAVA代碼：

（一）遞歸方法

設(shè)定中間位置為根節(jié)點(diǎn)（可以自己設(shè)定哪個作為根節(jié)點(diǎn)，所以有很多種的結(jié)果），選擇中間作為根節(jié)點(diǎn)可以保證高度平衡。
遞歸思路：
選擇中間位置所謂根節(jié)點(diǎn)，那么左邊所有的數(shù)字都小于它，作為左子樹。右邊所有的數(shù)字都大于它，作為右子樹。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return help(nums,0,nums.length-1);}public TreeNode help(int[] nums,int left,int right){if(left>right) return null;int mid = (left+right)/2;TreeNode root = new TreeNode(nums[mid]);root.left = help(nums,left,mid-1);root.right = help(nums,mid+1,right);return root;}
}