29_二叉搜索树中的插入操作

简介: 29_二叉搜索树中的插入操作

701.二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1:

输入:root = [4,2,7,1,3], val = 5
输出:[4,2,7,1,3,5]
解释:另一个满足题目要求可以通过的树是:

示例 2:

输入:root = [40,20,60,10,30,50,70], val = 25
输出:[40,20,60,10,30,50,70,null,null,25]

示例 3:

输入:root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出:[4,2,7,1,3,5]

【思路】

递归

递归三部曲:

  • 确定递归函数参数以及返回值
TreeNode insertIntoBST(TreeNode root, int val);
  • 确定终止条件
    终止条件就是找到遍历的节点为null的时候,就是要插入节点的位置了,并把插入的节点返回,代码如下:
if (root == null) 
  return new TreeNode(val);
  • 确定单层递归的逻辑
if (root.val > val) {
  root.left = insertInToBST(root.left, val);
}
if (root.val < val) {
  root.right = insertIntoBST(root.right, val);
}
return root;
  • 总结
    首先在二叉搜索树中的插入操作,大家不用恐惧其重构搜索树,其实根本不用重构。
    然后在递归中,我们重点讲了如何通过递归函数的返回值完成新加入节点和其父节点的赋值操作,并强调了搜索树的有序性。
    最后依然给出了迭代的方法,迭代的方法就需要记录当前遍历节点的父节点了,这个和没有返回值的递归函数实现的代码逻辑是一样的。
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode newRoot = root;
        TreeNode pre = root;
        while (root != null) {
            pre = root;
            if (root.val > val) {
                root = root.left;
            } else if (root.val < val) {
                root = root.right;
            } 
        }
        if (pre.val > val) {
            pre.left = new TreeNode(val);
        } else {
            pre.right = new TreeNode(val);
        }
        return newRoot;
    }
}
  • 递归法
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) // 如果当前节点为空,也就意味着val找到了合适的位置,此时创建节点直接返回。
            return new TreeNode(val);
            
        if (root.val < val){
            root.right = insertIntoBST(root.right, val); // 递归创建右子树
        }else if (root.val > val){
            root.left = insertIntoBST(root.left, val); // 递归创建左子树
        }
        return root;
    }
}
相关文章
|
人工智能 Java
零基础五步骤,从零开始天猫精灵
零基础五步骤,从零开始天猫精灵
1896 1
零基础五步骤,从零开始天猫精灵
|
JavaScript 数据处理
👻关于ECharts的那些事儿(数据超出Y轴最大值max又不想它隐藏)
👻关于ECharts的那些事儿(数据超出Y轴最大值max又不想它隐藏)
2389 0
|
JavaScript 关系型数据库 测试技术
接口文档管理神器RAP2安装和部署
一 RAP2 RAP2是在RAP1基础上重做的新项目,它包含两个组件(对应两个Github Repository)。 rap2-delos: 后端数据API服务器,基于Koa + MySQLlink rap2-dolores: 前端静态资源,基于React link 什么是RAP? rap是一款API 文档管理工具,在 RAP 中,可以定义接口的 URL、请求 & 响应细节格式等等。
14637 0
|
SQL Java 数据库连接
一篇文章彻底理解数据库的各种 JDBC 超时参数 1
一篇文章彻底理解数据库的各种 JDBC 超时参数
|
5月前
|
人工智能 持续交付 Python
个人如何用AI搭建轻量业务系统?内容、线索、知识库与交付流程
本文介绍个人如何用AI构建轻量业务系统:以内容入口为起点,串联线索收集、知识库沉淀、AI辅助沟通、模板化交付与数据复盘六大模块,用低代码/AI工具替代传统协作,以极低成本验证需求、积累经验、实现可持续交付。
|
存储 安全 小程序
Kali渗透测试:使用Word宏病毒进行渗透攻击
Kali渗透测试:使用Word宏病毒进行渗透攻击
819 1
Kali渗透测试:使用Word宏病毒进行渗透攻击
|
机器学习/深度学习 人工智能 安全
如何建设一支高效的人工智能团队
如何建设一支高效的人工智能团队
1670 0
如何建设一支高效的人工智能团队
为什么很多人都推荐IDM下载,idm比迅雷好在哪
现如今提到下载软件时,不可避免地要提到 IDM。似乎无论在哪一家的推荐软件榜单里,都能看到 IDM 的身影,随后便是对 IDM 强大功能的一系列介绍,像什么多线程下载速度超快、自动获取下载链接、嗅探功能直接在网页下载视频和音频……的确,它的功能非常的强大,但也不可忽视的是,它有一个最大的痛点——无法下载磁力连结和种子文件。
2634 0
为什么很多人都推荐IDM下载,idm比迅雷好在哪
|
机器学习/深度学习 缓存 架构师
十年技术进阶路,让我明白了三件要事(8000字长文)
8000字长文,大概花费您10分钟的阅读时间,我将以十年成长道路与八年写博经历分享与你,希望能给予各位读者或多或少的建议与提醒
1019 1
十年技术进阶路,让我明白了三件要事(8000字长文)
|
前端开发 架构师 Java
SpringBoot项目中WEB页面放哪里--【JSB系列之008】
SpringBoot项目中WEB页面放哪里--【JSB系列之008】