当前位置:网站首页>Leetcode 701 insertion operation in binary search tree -- recursive method and iterative method
Leetcode 701 insertion operation in binary search tree -- recursive method and iterative method
2022-07-06 05:46:00 【Hello, I'm Boger】
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/insert-into-a-binary-search-tree
The question :
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 .
Example 1:
Input :root = [4,2,7,1,3], val = 5
Output :[4,2,7,1,3,5]
explain : Another tree that meets the requirements of the topic is :
Example 2:
Input :root = [40,20,60,10,30,50,70], val = 25
Output :[40,20,60,10,30,50,70,null,null,25]
Example 3:
Input :root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output :[4,2,7,1,3,5]
Tips :
The number of nodes in the tree will be [0, 104] Within the scope of .
-108 <= Node.val <= 108
All worth Node.val yes unique Of .
-108 <= val <= 108
Guarantee val In primitive BST Does not exist in the .
Ideas :
In fact, I don't quite understand why this problem is classified as medium difficulty , Quite a simple question .
As long as you understand the concept of binary search tree , Search from the root node of the binary search tree , Until the location found is an empty node , Let's replace this empty node with a node with the value to be inserted .
We use recursive method and iterative method to solve this problem .
Recursive method Java Code :
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
TreeNode node = new TreeNode(val);
return node;
}
if (root.val > val) root.left = insertIntoBST(root.left, val);
if (root.val < val) root.right = insertIntoBST(root.right, val);
return root;
}
}
Iterative method Java Code :
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
TreeNode parent = root;
TreeNode cur = root;
while (cur != null) {
parent = cur;
if (cur.val > val) cur = cur.left;
else if (cur.val < val) cur = cur.right;
}
if (parent.val > val) parent.left = new TreeNode(val);
else if (parent.val < val) parent.right = new TreeNode(val);
return root;
}
}
边栏推荐
- PDK工藝庫安裝-CSMC
- 02. Develop data storage of blog project
- 无代码六月大事件|2022无代码探索者大会即将召开;AI增强型无代码工具推出...
- CoDeSys note 2: set coil and reset coil
- 清除浮动的方式
- Game push image / table /cv/nlp, multi-threaded start
- Web Security (V) what is a session? Why do I need a session?
- Zoom through the mouse wheel
- Go language -- language constants
- How to download GB files from Google cloud hard disk
猜你喜欢
[Tang Laoshi] C -- encapsulation: classes and objects
A master in the field of software architecture -- Reading Notes of the beauty of Architecture
进程和线程
How to download GB files from Google cloud hard disk
B站刘二大人-线性回归 Pytorch
High quality coding tool clion
C Advanced - data storage (Part 1)
Yygh-11-timing statistics
js Array 列表 实战使用总结
[SQL Server Express Way] - authentification et création et gestion de comptes utilisateurs
随机推荐
26file filter anonymous inner class and lambda optimization
Sword finger offer II 039 Maximum rectangular area of histogram
通讯录管理系统链表实现
初识数据库
Graduation design game mall
Processes and threads
Clear floating mode
B站刘二大人-反向传播
Game push image / table /cv/nlp, multi-threaded start
Installation de la Bibliothèque de processus PDK - csmc
嵌入式面试题(一:进程与线程)
P2802 go home
【云原生】3.1 Kubernetes平台安装KubeSpher
js Array 列表 实战使用总结
How can large websites choose better virtual machine service providers?
Station B Liu Erden linear regression pytoch
Anti shake and throttling are easy to understand
B站刘二大人-多元逻辑回归 Lecture 7
Station B, Mr. Liu Er - multiple logistic regression, structure 7
After the project is released, index Html is cached