当前位置:网站首页>leetcode刷题:二叉树26(二叉搜索树中的插入操作)
leetcode刷题:二叉树26(二叉搜索树中的插入操作)
2022-07-07 10:30:00 【涛涛英语学不进去】
701.二叉搜索树中的插入操作
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
提示:
- 给定的树上的节点数介于 0 和 10^4 之间
- 每个节点都有一个唯一整数值,取值范围从 0 到 10^8
- -10^8 <= val <= 10^8
- 新值和原始二叉搜索树中的任意节点值都不同
很简单的一题,按二叉搜索树的方式遍历,遇到叶子结点就直接判断大小,根据情况添加左或右;遇到单出度结点,先判断大小,如果是无出度的分支,则直接在本节点上添加新左或右结点,如果是有出度的分支,循环到那个结点再处理。
package com.programmercarl.tree;
/** * @ClassName InsertIntoBST * @Descriotion TODO * @Author nitaotao * @Date 2022/7/6 14:47 * @Version 1.0 * https://leetcode.cn/problems/insert-into-a-binary-search-tree/ * 701. 二叉搜索树中的插入操作 **/
public class InsertIntoBST {
public TreeNode insertIntoBST(TreeNode root, int val) {
//空根结点,就创建一个结点返回
if (root == null) {
return new TreeNode(val);
}
TreeNode node = root;
insert(node, val);
return root;
}
public void insert(TreeNode root, int val) {
//当前结点是叶子结点
if (root.left == null && root.right == null) {
if (root.val > val) {
//当前值比目标值大
root.left = new TreeNode(val);
} else {
root.right = new TreeNode(val);
}
return;
}
//单出度情况
if (root.left == null && root.right != null) {
if (root.val > val) {
//当前值比目标值大
root.left = new TreeNode(val);
return;
}
}
if (root.left != null && root.right == null) {
if (root.val < val) {
//当前值比目标值小
root.right = new TreeNode(val);
return;
}
}
if (root.val > val) {
//当前值比目标值大
insert(root.left, val);
} else {
insert(root.right, val);
}
}
}
边栏推荐
- [statistical learning methods] learning notes - improvement methods
- Problem: the string and characters are typed successively, and the results conflict
- DOM parsing XML error: content is not allowed in Prolog
- 顶级域名有哪些?是如何分类的?
- SQL Lab (46~53) (continuous update later) order by injection
- What are the technical differences in source code anti disclosure
- Introduction to three methods of anti red domain name generation
- 普乐蛙小型5d电影设备|5d电影动感电影体验馆|VR景区影院设备
- The left-hand side of an assignment expression may not be an optional property access.ts(2779)
- Tutorial on the principle and application of database system (011) -- relational database
猜你喜欢
In the small skin panel, use CMD to enter the MySQL command, including the MySQL error unknown variable 'secure_ file_ Priv 'solution (super detailed)
What is an esp/msr partition and how to create an esp/msr partition
College entrance examination composition, high-frequency mention of science and Technology
<No. 9> 1805. 字符串中不同整数的数目 (简单)
金融数据获取(三)当爬虫遇上要鼠标滚轮滚动才会刷新数据的网页(保姆级教程)
The left-hand side of an assignment expression may not be an optional property access.ts(2779)
千人规模互联网公司研发效能成功之路
Static comprehensive experiment
EPP+DIS学习之路(1)——Hello world!
SQL Lab (46~53) (continuous update later) order by injection
随机推荐
Epp+dis learning path (1) -- Hello world!
即刻报名|飞桨黑客马拉松第三期盛夏登场,等你挑战
Introduction and application of smoothstep in unity: optimization of dissolution effect
利用栈来实现二进制转化为十进制
问题:先后键入字符串和字符,结果发生冲突
wallys/Qualcomm IPQ8072A networking SBC supports dual 10GbE, WiFi 6
BGP third experiment report
密码学系列之:在线证书状态协议OCSP详解
什么是ESP/MSR 分区,如何建立ESP/MSR 分区
gcc 编译报错
Will the filing free server affect the ranking and weight of the website?
Solve server returns invalid timezone Go to ‘Advanced’ tab and set ‘serverTimezone’ property manually
Sonar:Cognitive Complexity认知复杂度
《看完就懂系列》天哪!搞懂节流与防抖竟简单如斯~
数据库系统原理与应用教程(010)—— 概念模型与数据模型练习题
VSCode的学习使用
[play RT thread] RT thread Studio - key control motor forward and reverse rotation, buzzer
数据库系统原理与应用教程(007)—— 数据库相关概念
@What happens if bean and @component are used on the same class?
zero-shot, one-shot和few-shot