JAVA练习310- 将有序数组转换为二叉搜索树

题目概览给你一个整数数组nums其中元素已经按升序排列请你将其转换为一棵 平衡 二叉搜索树。平衡二叉树是指该树所有节点的左右子树的高度相差不超过 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^4nums按严格递增顺序排列来源108. 将有序数组转换为二叉搜索树 - 力扣LeetCode解题分析方法二分法二叉搜索树是左边元素 根节点 右边元素因此我们可以用二分法将数组的中间元素作为根节点将数组拆分为两个子数组两个子数组和左右两个节点再进行相同的操作直到子数组长度为 0。时间复杂度O(n)空间复杂度O(n)/** * 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 sortedArrayToBST(nums, 0, nums.length - 1); } public TreeNode sortedArrayToBST(int[] nums, int i, int j) { if (i j) { return null; } int mid (i j) / 2; TreeNode node new TreeNode(nums[mid]); node.left sortedArrayToBST(nums, i, mid - 1); node.right sortedArrayToBST(nums, mid 1, j); return node; } }