问题描述:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
原问题链接:https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
问题分析
因为这里要求将排序后的数组转换成高度平衡的二叉搜索树,所以这里转换的时候,每次取的元素节点必须要尽量保证它的左右子树的元素个数是一样的。只有这样才能达到一个尽量平衡的结果。于是我们可以每次去数组中给定范围内的中间元素mid,然后从l到mid - 1的元素递归的去构造它的左子树,从mid + 1到r的范围递归的构造它的右子树。
按照这个思路,可以很快得到如下的代码:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { if(nums == null || nums.length == 0) return null; return sortedArrayToBST(nums, 0, nums.length - 1); } public TreeNode sortedArrayToBST(int[] nums, int l, int r) { if(l > r) return null; int mid = l + (r - l) / 2; TreeNode node = new TreeNode(nums[mid]); node.left = sortedArrayToBST(nums, l, mid - 1); node.right = sortedArrayToBST(nums, mid + 1, r); return node; } }
相关推荐
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary...
leetcode卡 leetcode exercises 3-5 solutions everyday. fighting~ TODO array Best Time to Buy and Sell Stock II Valid Sudoku linked list Palindrome linked list Linked List Cycle trees Convert Sorted ...
leetcode的题目:Balanced Binary Tree
leetcode LeetCode刷题 题号是LeetCode原题,题目是自己的解答 Easy 题号 题目 Tags Star Company HashMap :star: :star: :star: Integer :star: :star: String :star: String、Stack :star: :star: :star: ...
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
LeetCode Remove Duplicates from Sorted Array解决方案
leetcode添加元素使和等于 LeetCode leetcode 指针类型题目 1. 链表 函数参数传入的链表都没有链表的头,从第一个有数据的节点开始 函数返回一个链表,这个链表也没有头 2. 内存分配 二维数组内存分配 二维数组分配...
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 ...
array_leetcode leetcode刷题总结,此部分是array #第一题 问题: Given an array of integers, return indices of the two numbers such that they add up to a specific target. 程序: #include using namespace ...
LeetCode::laptop:LeetCode解决方案
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
leetcode卡leetcode 算法 :smiling_face_with_sunglasses: 9月打卡 问题 困难 标签 Medium Minimax Dynamic Programming Medium Minimax Dynamic Programming Math Hard BackTracking Easy Tree Depth-first Search ...
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
什么水平能刷leetcode leetcode :woman_biking: I like to brush leetcode, it is a way of my pastime. I really enjoy it, I will always update it. :open_book: :raised_fist: 不间断刷题天数:1天 :elephant: ...
leetcode题目:Best Time to Buy and Sell Stock II
LeetCode Merge 2 Sorted Lists解决方案
LeetCode 在LeetCode和其他编码平台上解决的问题的集合