领扣LintCode算法问题答案-1359. 有序数组转换为二叉搜索树
目录
- 1359. 有序数组转换为二叉搜索树
-
- 描述
- 样例 1：
- 样例 2：
- 题解
- 鸣谢
1359. 有序数组转换为二叉搜索树
描述
给定一个数组，其中元素按升序排序，将其转换为高度平衡的BST。
对于这个问题，高度平衡的二叉树被定义为二叉树，其中每个节点的两个子树的深度从不相差超过1。
样例 1：
输入: [-10,-3,0,5,9],
输出: [0,-3,9,-10,#,5],
解释:
针对该数组的其中一个解为 [0,-3,9,-10,null,5], 其对应的平衡BST树如下:0/ \-3 9/ /-10 5
样例 2：
输入: [1,3]
输出: [3,1]
解释:
针对该数组的其中一个解为 [3,1], 其对应的平衡BST树如下:3/
1
题解
/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/public class Solution {
/*** @param nums: the sorted array* @return: the root of the tree*/public TreeNode convertSortedArraytoBinarySearchTree(int[] nums) {
// Write your code here.if (nums == null|| nums.length == 0) {
return null;}int mid = (nums.length - 1) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = convertSortedArraytoBinarySearchTree(nums, 0, mid - 1);root.right = convertSortedArraytoBinarySearchTree(nums, mid + 1, nums.length - 1);return root;}private TreeNode convertSortedArraytoBinarySearchTree(int[] nums, int startIndex, int endIndex) {
if (startIndex > endIndex|| startIndex < 0|| endIndex >= nums.length) {
return null;}int mid = (startIndex + endIndex) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = convertSortedArraytoBinarySearchTree(nums, startIndex, mid - 1);root.right = convertSortedArraytoBinarySearchTree(nums, mid + 1, endIndex);return root;}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。
欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。