[模版总结] - 树的基本算法2 - BST

BST定义

BST - Binary Search Tree, 即二叉搜索树(有序二叉树)

特性

  • 中序遍历有序
  • 查找/插入/删除某个数值可以通过O(h) 即树的高度,最优logN,最坏 N.
    • 有多种改进BST可以动态维持插入删除后树结构能尽可能保持平衡

BST vs. 有序数组 vs. 普通数组 - 引用自 古城算法 https://www.youtube.com/watch?v=DpkTu2tU87o&list=PLbaIOC0vpjNVHmklf0nzPlPsNvJiqq1lZ&index=3

BST基本操作

查询 - 二分查找

  • 搜索数值 - 二分法
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null) {
            if (root.val<val) {
                root = root.right;
            } else if (root.val>val) {
                root = root.left;
            } else {
                return root;
            }
        }
        return null;      
    }
}
  • 搜索临近数值
class Solution {
    double min = Double.MAX_VALUE;
    int res = -1;
    public int closestValue(TreeNode root, double target) {
        dfs(root, target);
        return res;
    }

    private void dfs(TreeNode root, double target) {
        if (root==null) return;

        if (Math.abs(root.val - target) < min) {
            min = Math.abs(root.val - target);
            res = root.val;
        } else if (Math.abs(root.val - target) == min) {
            res = root.val<res? root.val: res;
        }

        if (root.val>target) dfs(root.left, target);
        else dfs(root.right, target);

    }
}

插入

插入则是首先找到需要插入的位置,然后插入新结点

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        return dfs(root, val);
    }

    private TreeNode dfs(TreeNode root, int val) {
        if (root==null) {
            root = new TreeNode(val);
            return root;
        }

        if (root.val > val) root.left = dfs(root.left, val);
        else root.right = dfs(root.right, val);

        return root; 
    }
}

删除

删除操作较为复杂一点,我们在删除之后还需要维护当前二叉搜索树的性质,有三种情况:

  1. 删除叶子结点,不会影响BST性质,直接删除即可
  2. 删除结点没有右子树,也就是删除后左子树不会影响BST性质,将左子树root直接顶替删除结点的位置即可
  3. 删除结点有左右子树,为了保证BST性质,我们选择删除点的后继结点作为顶替结点,也就是删除结点右子树最左边的那个点,因为可以保证右子树所有点都大于该点,维持了BST性质
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        /**
        删除三种情况
        1. 叶子结点
        2. 只存在一个子树
        3. 左右都存在子树
         */

        return dfs(root, key);

        

    }

    private TreeNode dfs(TreeNode root, int key) {
        if (root==null) return null;

        if (root.val==key) {
            if (root.left==null && root.right==null) return null;
            else if (root.left==null || root.right==null) {
                if (root.left!=null) return root.left;
                if (root.right!=null) return root.right;
            } else {
                // 找到root的后继结点,也就是右子树最左边的那个点
                TreeNode dum = root.right;
                while (dum.left!=null) {
                    dum = dum.left;
                }
                root.val = dum.val;
                root.right = dfs(root.right, root.val);
            }
        } else if (root.val>key) {
            root.left = dfs(root.left, key);
        } else {
            root.right = dfs(root.right, key);
        }

        return root;
    }
}

前驱/后继结点

Leetcode 285

求解某一个点的前驱结点思路存储一个变量prev来保存进行下一层递归前的结点信息,如果中序遍历递归遍历到目标结点,其实保存的prev就是该结点的前驱结点

private void preSuccessor(TreeNode root, TreeNode p) {
    if (node==null) return;

    preSuccessor(node.left, p);
    if (root==p) return prev;
    prev = root;

    preSuccessor(node.right, p);
}

求解后躯结点较为复杂,需要考虑到几种情况:

  1. 目标结点有右子树,那么后继结点则是右子树中leftmost结点
  2. 如果目标结点没有右子树,那么后继结点则可能是parent中的某个结点

求解上述第二类后继结点思路类似,前驱结点是当前递归层处理的结点是目标结点时,prev保存的值即为前驱结点;后继结点可以理解为当前递归层的前驱结点时目标结点时,那么当前结点就是目标结点的后继结点,有点逆向思维哈哈。

 

class Solution {
    // 需要前驱结点信息
    TreeNode prev;
    TreeNode insuccessor;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (p.right!=null) {
            TreeNode node = p.right;
            while (node.left!=null) {
                node = node.left;
            }
            return node;
        } else {
            helper(root, p);
        }

        return insuccessor;
    }

    private void helper(TreeNode node, TreeNode p) {
        if (node==null) return;

        helper(node.left, p);
        // check 当前结点
        if (prev!=null && prev==p) {
            insuccessor = node;
        }
        prev = node; //如果 当前结点前驱结点==p那么这个结点就是p的后驱结点
        helper(node.right, p);
    }
}

验证是否为BST

Leetcode 98. Validate BST

基本思路就是确保左结点 < 根结点 < 右结点,但是还需要保证局部正确的同时,左子树全部结点 < 根结点 < 右子树全部结点。所以每一次向下递归左子树时要以当前结点值作为上限值,遍历右子树时以当前结点值作为下限值

class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    private boolean helper(TreeNode root, Integer low, Integer high) {
        if (root==null) return true;

        if ((low!=null && root.val<=low) || (high!=null && root.val>=high)) {
            return false;
        }

        return helper(root.left, low, root.val) && helper(root.right, root.val, high);
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/156045.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

有Mac或无Mac电脑通用的获取安卓公钥的方案

从2023年9月开始&#xff0c;所有上架应用市场的app都需要进行APP备案。 其中后端服务器在阿里云的可以在阿里云备案&#xff0c;后端服务器在腾讯云的可以在腾讯云备案。但无论你是在什么云厂商里做备案&#xff0c;无一例外的是&#xff0c;无论是上架安卓应用还是上架IOS应…

Python大数据学习问题整理汇总

day01 分区表与分桶表的区别 在这里插入代码片day02 数据仓分层/与本质 数据仓库(OLAP)的本质叫联机分析处理, 一般针对某些主题的历史数据进行分析 主要面向分析,支持管理决策。源数据层&#xff08;ODS&#xff09;&#xff1a; 此层数据无任何更改&#xff0c;直接沿用外围…

【2021集创赛】基于arm Cortex-M3处理器与深度学习加速器的实时人脸口罩检测 SoC

团队介绍 参赛单位&#xff1a;深圳大学 队伍名称&#xff1a;光之巨人队 指导老师&#xff1a;钟世达、袁涛 参赛队员&#xff1a;冯昊港、潘家豪、慕镐泽 图1 团队风采 1. 项目简介 新冠疫情席卷全球&#xff0c;有效佩戴口罩可以极大程度地减小病毒感染的风险。本项目开发…

JWT登录认证(3拦截器)

Jwt登录认证&#xff08;拦截器&#xff09;&#xff1a; 使用拦截器统一验证令牌 登录和注册接口需要放行 interceptors.LoginInterceptor&#xff1a;&#xff08;注册一个拦截器&#xff09; package com.lin.springboot01.interceptors;import com.lin.springboot01.pojo.…

wpf devexpress添加TreeListControl到项目

此教程示范如何添加TreeListControl到项目和绑定控件自引用数据源&#xff1a; 添加数据模型 绑定tree&#xff0c;并添加如下字段到数据源对象&#xff1a; Key字段包含唯一值索引节点 Parent字段包含父索引节点 添加数据模型&#xff08;Employee和Staff类&#xff09;到…

物理驱动深度学习方法总结

一、物理驱动深度学习方法总结 现有博主更新物理驱动深度学方法总体介绍 二、 PINN介绍 PINN综述Blog介绍&#xff1a;内嵌物理知识神经网络 &#xff08;Physics Informed Neural Network&#xff0c;简称PINN&#xff09; 是一种科学机器在传统数值领域的应用方法&…

软件测试基础 —— 单元测试

Hello&#xff01;大家好&#xff0c;我是BugBear&#xff0c;一个专注于分享软件测试干货的测试开发。 对于软件测试&#xff0c;我们先按照开发阶段来进行划分&#xff0c;将软件测试分为单元测试、集成测试、系统测试、验收测试&#xff0c;下面我们来聊聊单元测试。 1、什…

JVM-HotSpot虚拟机对象探秘

目录 一、对象的实例化 &#xff08;一&#xff09;创建对象的方式 &#xff08;二&#xff09;创建对象的步骤 二、对象的内存布局 &#xff08;一&#xff09;对象头 &#xff08;二&#xff09;实例数据 &#xff08;三&#xff09;对齐填充 三、 对象的访问定位 &…

小迈迈驰组态软件支持国产龙芯2K1000等处理器

自2019年起&#xff0c;南京迈思德电气自动化有限公司组织研发团队&#xff0c;进行跨平台组态软件的研发&#xff0c;适配国产处理器&#xff0c;目前已经完成单机版产品的研发&#xff0c;并在基于龙芯2K1000处理器[Loongnix操作系统]的加固人机界面产品上应用。 Loongnix是龙…

可逆矩阵的性质

如果矩阵A可逆&#xff0c;那么它的逆矩阵也可逆&#xff0c;并且如果矩阵A可逆&#xff0c;假设是一个不为0的数&#xff0c;那么也可逆&#xff0c;并且如果矩阵A和都可逆&#xff0c;而且它们的阶数也相同&#xff0c;那么它们的乘积也是可逆的&#xff0c;并且如果矩阵A可逆…

docker数据卷详细讲解及数据卷常用命令

docker数据卷详细讲解及数据卷常用命令 Docker 数据卷是一种将宿主机的目录或文件直接映射到容器中的特殊目录&#xff0c;用于实现数据的持久化和共享。Docker 数据卷有以下特点&#xff1a; 数据卷可以在一个或多个容器之间共享和重用&#xff0c;不受容器的生命周期影响。…

<Linux>(极简关键、省时省力)《Linux操作系统原理分析之Linux 进程管理 2》(6)

《Linux操作系统原理分析之Linux 进程管理 2》&#xff08;6&#xff09; 4 Linux 进程管理4.2 Linux 进程的状态和标识4.2.1 Linux 进程的状态及转换4.2.2 Linux 进程的标识4.2.3 进程标识哈希表 4 Linux 进程管理 4.2 Linux 进程的状态和标识 4.2.1 Linux 进程的状态及转换…

提高Producer的发送速度

发送一条消息出去要经过三步&#xff0c;一是客户端发送请求到服务器&#xff0c;二是服务器处理该请求&#xff0c;三是服务器向客户端返回应答&#xff0c;一次消息的发送耗时是上述三个步骤的总和。在一些对速度要求高&#xff0c;但是可靠性要求不高的场景下&#xff0c;比…

2023年中国机动车拍卖网络化趋势加速,网络拍卖专场数量大幅上升至47489场[图]

2022年&#xff0c;由于机动车拍卖网络化趋势继续加速&#xff0c;网络拍卖专场数量大幅上升&#xff0c;全国机动车专场拍卖会高达59450场&#xff0c;较上年攀升125.31%。在389家拍卖企业中&#xff0c;举办场次超过100场的企业有27家&#xff0c;合计54850场&#xff0c;占比…

11.4MyBatis(基础)

一.搭环境 1.创建完SSM项目,添加MySQL和MyBatis后,项目启动一定会报错,这是正常情况. 2.配置文件 properties: server.port9090 spring.datasource.urljdbc:mysql://127.0.0.1:3306/test1?characterEncodingutf8&useSSLfalse spring.datasource.usernameroot spring.d…

快速入门:构建您的第一个 .NET Aspire 应用程序

##前言 云原生应用程序通常需要连接到各种服务&#xff0c;例如数据库、存储和缓存解决方案、消息传递提供商或其他 Web 服务。.NET Aspire 旨在简化这些类型服务之间的连接和配置。在本快速入门中&#xff0c;您将了解如何创建 .NET Aspire Starter 应用程序模板解决方案。 …

贪吃蛇、俄罗斯方块

贪吃蛇 一、创建新项目 创建一个新的项目&#xff0c;并命名。 创建一个名为images的文件夹用来存放游戏相关图片。 然后再在项目的src文件下创建一个com.xxx.view的包用来存放所有的图形界面类&#xff0c; 创建一个com.xxx.controller的包用来存放启动的入口类(控制类) 二…

通信原理板块——脉冲编码调制(PCM)

微信公众号上线&#xff0c;搜索公众号小灰灰的FPGA,关注可获取相关源码&#xff0c;定期更新有关FPGA的项目以及开源项目源码&#xff0c;包括但不限于各类检测芯片驱动、低速接口驱动、高速接口驱动、数据信号处理、图像处理以及AXI总线等 1、脉冲编码调制PCM原理 将模拟信号…

C++第一讲:起源和规范

面向过程和面向对象 大千世界中&#xff0c;事务的发展规律都是面向过程的状态。例如一颗种子从生根到发芽&#xff0c;从发芽到开花&#xff0c;从开花到结果。 但是面向过程是一个更贴近**“机械”**的表达方式&#xff0c;而更贴近人类思想的却是面向对象的表达方式。 以…

2023年中国冲击波治疗仪市场发展趋势分析:未来市场增长空间更大[图]

冲击波在临床医学领域最早应用于体外冲击波碎石&#xff0c;在二十世纪八十年代末期&#xff0c;体外冲击波碎石技术开始被运用到骨科及康复理疗领域&#xff0c;经过十余年的临床研究&#xff0c;冲击波疗法日益完善&#xff0c;应用范围也日益扩大。冲击波作为一种介于保守疗…