LeetCode:将有序数组转换为二叉搜索树【108】
2024-08-28 15:27:22
LeetCode:将有序数组转换为二叉搜索树【108】
题目描述
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9], 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0
/ \
-3 9
/ /
-10 5
题目分析
BST树的建立是唯一的吗?即使给定有序数组,我认为BST也是是不唯一的。
二叉树的建立过程就是不断取中间值,然后将数组再一拆为二,然后左边部分找左子节点,右边部分找右子节点,循此往复就可建立完成。
Java题解
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length==0)
return null;
return BST(nums,0,nums.length-1);
} public TreeNode BST(int[] nums,int lo,int hi)
{
if(lo>hi)
return null;
int mid = (hi-lo)/2+lo;
TreeNode node = new TreeNode(nums[mid]);
node.left = BST(nums,lo,mid-1);
node.right = BST(nums,mid+1,hi);
return node;
} }
最新文章
- 汉字正则表达式[\u4E00-\u9FFF]原因
- SpringMVC 邮件发送
- 学习Spring(二) 调用静态工厂方法创建Bean
- yourphp超出20记录自动删除
- Java并发包源码学习之线程池(一)ThreadPoolExecutor源码分析
- CPU时间戳获取
- mysql_multi启动数据库
- POJ 1459 Power Network 最大流(Edmonds_Karp算法)
- 根据IP地址获取IP的详细信息
- 【转】ASP.NET MVC框架下使用MVVM模式-KnockOutJS+JQ模板例子
- MySQL 一些小知识
- 阿里巴巴 web前端性能优化进阶路
- hdu_4787_GRE Words Revenge(在线AC自动机)
- 记一些让footer始终位于网页底部的方法
- asp.net core 系列 7 Razor框架路由(上)
- idea: Unable to parse template ";class";
- 扩展Linux磁盘空间
- expect学习笔记及实例详解【转】
- clojure中符号symbols 和变量vars的正确理解
- SharePoint CAML In Action——Part II