当前位置:网站首页>Recursive method converts ordered array into binary search tree
Recursive method converts ordered array into binary search tree
2022-07-06 00:50:00 【Hydrion-Qlz】
108. Convert an ordered array to a binary search tree
The difficulty is simple
Give you an array of integers nums
, Where elements have been Ascending array , Please turn it into a Highly balanced Binary search tree .
Highly balanced A binary tree is a tree that satisfies 「 The absolute value of the height difference between the left and right subtrees of each node does not exceed 1 」 Two fork tree .
Ideas
The title says that it should be converted into a highly balanced binary search tree . What's the difference between this and converting to an ordinary binary search tree ?
If it is balanced, we will naturally think of dividing the array from the middle of the array , Take the intermediate element as the root node , Use the left node to construct the left subtree , Use the nodes on the right to construct the right subtree , Then recursively construct the elements on the left and right , Until the interval length is 0 until .
This is very similar to dichotomy , Half and half treatment .
Then you need to pay attention to the scope you define , It is suggested to uniformly use the form of left closed right open or both left and right closed in your own coding , Don't switch between the two , It's easy to get dizzy
package cn.edu.xjtu.carlWay.tree.array2BST;
import cn.edu.xjtu.Util.TreeNode.TreeNode;
/** * 108. Convert an ordered array to a binary search tree * Give you an array of integers nums , Where elements have been Ascending array , Please turn it into a Highly balanced Binary search tree . * <p> * Highly balanced A binary tree is a tree that satisfies 「 The absolute value of the height difference between the left and right subtrees of each node does not exceed 1 」 Two fork tree . * <p> * https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/ */
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helpBuild(nums, 0, nums.length);
}
// The range here is left closed and right open , It's especially necessary to understand this
private TreeNode helpBuild(int[] nums, int left, int right) {
if (left == right) {
return null;
}
if (right - left == 1) {
return new TreeNode(nums[left]);
}
// Find the middle root node
int idx = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[idx]);
// Construct the left subtree
node.left = helpBuild(nums, left, idx);
// Construct the right subtree
node.right = helpBuild(nums, idx + 1, right);
return node;
}
}
边栏推荐
- A preliminary study of geojson
- Exciting, 2022 open atom global open source summit registration is hot
- 几百行代码实现一个 JSON 解析器
- [groovy] XML serialization (use markupbuilder to generate XML data | set XML tag content | set XML tag attributes)
- MCU通过UART实现OTA在线升级流程
- OpenCV经典100题
- 激动人心,2022开放原子全球开源峰会报名火热开启
- The detailed page returns to the list and retains the original position of the scroll bar
- Spark获取DataFrame中列的方式--col,$,column,apply
- 如何利用Flutter框架开发运行小程序
猜你喜欢
[groovy] compile time meta programming (AST syntax tree conversion with annotations | define annotations and use groovyasttransformationclass to indicate ast conversion interface | ast conversion inte
【EI会议分享】2022年第三届智能制造与自动化前沿国际会议(CFIMA 2022)
[groovy] XML serialization (use markupbuilder to generate XML data | create sub tags under tag closures | use markupbuilderhelper to add XML comments)
SAP Spartacus home 页面读取 product 数据的请求的 population 逻辑
[groovy] JSON serialization (jsonbuilder builder | generates JSON string with root node name | generates JSON string without root node name)
After Luke zettlemoyer, head of meta AI Seattle research | trillion parameters, will the large model continue to grow?
猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
看抖音直播Beyond演唱会有感
Ffmpeg captures RTSP images for image analysis
Spark SQL null value, Nan judgment and processing
随机推荐
RAID disk redundancy queue
Logstash clear sincedb_ Path upload records and retransmit log data
esxi的安装和使用
Keepalive component cache does not take effect
The detailed page returns to the list and retains the original position of the scroll bar
logstash清除sincedb_path上传记录,重传日志数据
Idea远程提交spark任务到yarn集群
The population logic of the request to read product data on the sap Spartacus home page
激动人心,2022开放原子全球开源峰会报名火热开启
Basic introduction and source code analysis of webrtc threads
Calculate sha256 value of data or file based on crypto++
Promise
Analysis of the combination of small program technology advantages and industrial Internet
I'm interested in watching Tiktok live beyond concert
Exciting, 2022 open atom global open source summit registration is hot
如何制作自己的机器人
云导DNS和知识科普以及课堂笔记
如何制作自己的機器人
[groovy] compile time metaprogramming (compile time method injection | method injection using buildfromspec, buildfromstring, buildfromcode)
小程序容器可以发挥的价值