当前位置:网站首页>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;
}
}
边栏推荐
- FFmpeg抓取RTSP图像进行图像分析
- How spark gets columns in dataframe --column, $, column, apply
- [groovy] compile time meta programming (compile time method interception | method interception in myasttransformation visit method)
- Pointer - character pointer
- devkit入门
- Spark-SQL UDF函数
- 云导DNS和知识科普以及课堂笔记
- [groovy] compile time metaprogramming (compile time method injection | method injection using buildfromspec, buildfromstring, buildfromcode)
- Free chat robot API
- Ffmpeg captures RTSP images for image analysis
猜你喜欢
Cve-2017-11882 reappearance
Introduction of motor
看抖音直播Beyond演唱会有感
cf:H. Maximal AND【位运算练习 + k次操作 + 最大And】
测试/开发程序员的成长路线,全局思考问题的问题......
XML Configuration File
I'm interested in watching Tiktok live beyond concert
[groovy] XML serialization (use markupbuilder to generate XML data | create sub tags under tag closures | use markupbuilderhelper to add XML comments)
Arduino hexapod robot
The population logic of the request to read product data on the sap Spartacus home page
随机推荐
Anconda download + add Tsinghua +tensorflow installation +no module named 'tensorflow' +kernelrestart: restart failed, kernel restart failed
Spark DF adds a column
Cannot resolve symbol error
程序员搞开源,读什么书最合适?
NLP text processing: lemma [English] [put the deformation of various types of words into one form] [wet- > go; are- > be]
程序员成长第九篇:真实项目中的注意事项
cf:C. The Third Problem【关于排列这件事】
Folding and sinking sand -- weekly record of ETF
Reading notes of the beauty of programming
The value of applet containers
For a deadline, the IT fellow graduated from Tsinghua suddenly died on the toilet
Why can't mathematics give machine consciousness
[groovy] XML serialization (use markupbuilder to generate XML data | create sub tags under tag closures | use markupbuilderhelper to add XML comments)
devkit入门
Mobilenet series (5): use pytorch to build mobilenetv3 and learn and train based on migration
Spark SQL null value, Nan judgment and processing
Introduction of motor
Yolov5、Pycharm、Anaconda环境安装
golang mqtt/stomp/nats/amqp
Installation and use of esxi