当前位置:网站首页>Recursive method to realize the insertion operation in binary search tree
Recursive method to realize the insertion operation in binary search tree
2022-07-06 00:51:00 【Hydrion-Qlz】
701. Insert operation in binary search tree
difficulty : secondary
Given a binary search tree (BST) The root node root
And the value to be inserted into the tree value
, Insert values into a binary search tree . Return to the root node of the binary search tree after insertion . input data Guarantee , The new value is different from any node value in the original binary search tree .
Be careful , There may be many effective insertion methods , As long as the tree remains a binary search tree after insertion . You can go back to Any valid result .
Ideas
towards BST When inserting a value in, you need to determine the size of the inserted value and the value of the current node
- If the insertion value is less than the value of the current node , Then find the right position in the left subtree of the current node
- If the insertion value is greater than the value of the current node , Then find a suitable position in the right subtree of the current node
If the code of solution one below is difficult to understand , You can look at the code of solution 2 first
Solution 1 :
package cn.edu.xjtu.carlWay.tree.insertIntoBST;
import cn.edu.xjtu.Util.TreeNode.TreeNode;
/** * 701. Insert operation in binary search tree * Given a binary search tree (BST) The root node root And the value to be inserted into the tree value , Insert values into a binary search tree . Return to the root node of the binary search tree after insertion . input data Guarantee , The new value is different from any node value in the original binary search tree . * <p> * Be careful , There may be many effective insertion methods , As long as the tree remains a binary search tree after insertion . You can go back to Any valid result . * <p> * https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/ */
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) // If the current node is empty , That means val Found the right place , At this point, the created node returns directly to .
return new TreeNode(val);
if (root.val < val){
root.right = insertIntoBST(root.right, val); // Recursively create the right subtree
}else if (root.val > val){
root.left = insertIntoBST(root.left, val); // Recursively create left subtree
}
return root;
}
}
Solution 2 :
If the left child node is empty, insert , If it's not empty, keep looking , The same goes for the right side
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (root.val > val) {
if (root.left == null) {
root.left = new TreeNode(val);
} else {
insertIntoBST(root.left, val);
}
} else {
if (root.right == null) {
root.right = new TreeNode(val);
} else {
insertIntoBST(root.right, val);
}
}
return root;
}
边栏推荐
- uniapp开发,打包成H5部署到服务器
- A preliminary study of geojson
- [EI conference sharing] the Third International Conference on intelligent manufacturing and automation frontier in 2022 (cfima 2022)
- Overview of Zhuhai purification laboratory construction details
- anconda下载+添加清华+tensorflow 安装+No module named ‘tensorflow‘+KernelRestarter: restart failed,内核重启失败
- Kotlin core programming - algebraic data types and pattern matching (3)
- MySQL storage engine
- NLP basic task word segmentation third party Library: ICTCLAS [the third party library with the highest accuracy of Chinese word segmentation] [Chinese Academy of Sciences] [charge]
- Intensive learning weekly, issue 52: depth cuprl, distspectrl & double deep q-network
- 《强化学习周刊》第52期:Depth-CUPRL、DistSPECTRL & Double Deep Q-Network
猜你喜欢
2022-02-13 work record -- PHP parsing rich text
Data analysis thinking analysis methods and business knowledge - analysis methods (III)
Model analysis of establishment time and holding time
免费的聊天机器人API
Extension and application of timestamp
Spark SQL null value, Nan judgment and processing
Introduction of motor
图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
How to use the flutter framework to develop and run small programs
KDD 2022 | 脑电AI助力癫痫疾病诊断
随机推荐
devkit入门
synchronized 和 ReentrantLock
Illustrated network: the principle behind TCP three-time handshake, why can't two-time handshake?
A preliminary study of geojson
Mobilenet series (5): use pytorch to build mobilenetv3 and learn and train based on migration
Power query data format conversion, Split Merge extraction, delete duplicates, delete errors, transpose and reverse, perspective and reverse perspective
curlpost-php
Spark AQE
NLP generation model 2017: Why are those in transformer
Zhuhai's waste gas treatment scheme was exposed
Problems and solutions of converting date into specified string in date class
Idea远程提交spark任务到yarn集群
OpenCV经典100题
新手入门深度学习 | 3-6:优化器optimizers
Data analysis thinking analysis methods and business knowledge - analysis methods (III)
Uniapp development, packaged as H5 and deployed to the server
【线上小工具】开发过程中会用到的线上小工具合集
猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
Spark SQL空值Null,NaN判断和处理
Construction plan of Zhuhai food physical and chemical testing laboratory