领扣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; } }

原题链接点这里

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。