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;
    }
}
相关文章
|
域名解析 负载均衡 架构师
Nginx极简入门(六)配置Nginx负载均衡,提高系统并发性能!
前面讲了如何配置Nginx虚拟主机、如何配置反向代理。Nginx最主要的功能就是反向代理和负载均衡。今天要说的是如何配置nginx和tomcat实现反向代理。
Nginx极简入门(六)配置Nginx负载均衡,提高系统并发性能!
|
11月前
|
监控 负载均衡 Java
5 大 SpringCloud 核心组件详解,8 张图彻底弄懂
本文图文详解 Spring Cloud 的五大核心组件,帮助深入理解和掌握微服务架构。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
5 大 SpringCloud 核心组件详解,8 张图彻底弄懂
|
9月前
|
人工智能 数据处理 C#
AI Dev Gallery:微软开源 Windows AI 模型本地运行工具包和示例库,助理开发者快速集成 AI 功能
微软推出的AI Dev Gallery,为Windows开发者提供开源AI工具包和示例库,支持本地运行AI模型,提升开发效率。
431 13
|
C语言
C语言中的复合语句
C语言中的复合语句
1059 1
|
SQL Java 数据库连接
【MyBatisPlus】通俗易懂 快速入门 详细教程
【MyBatisPlus】通俗易懂 快速入门 详细教程
1258 0
|
Python
python获取音频时长
python获取音频时长
545 0
|
存储 数据采集 人工智能
深度探索Aidlux智慧教育中的图像版面分析应用实践
本文详细描述了智慧教育领域的版面分析应用的人工智能训练营项目。项目的目标是构建一个高效的文档图像处理系统,实现文档对象识别和分类,并探索了组卷、以题搜题、文档电子化存储、结构化解析等功能。通过训练模型、实践应用和模型部署验证,分享了在该项目中所获得的见解和心得。
250 0
|
人工智能 运维 中间件
推荐一位阿里朋友的巨作,助你成为顶尖服务端开发者——《服务端开发:技术、方法与实用解决方案》
推荐一位阿里朋友的巨作,助你成为顶尖服务端开发者——《服务端开发:技术、方法与实用解决方案》
767 0
|
机器学习/深度学习 人工智能 达摩院
2442 个专业术语!人工智能术语库 AITD 更新至 3.1 版
2442 个专业术语!人工智能术语库 AITD 更新至 3.1 版
3658 0