代码随想录算法刷题训练营day23

代码随想录算法刷题训练营day23:LeetCode(669)修剪二叉搜索树、LeetCode(108)将有序数组转换为二叉搜索树、LeetCode(538)把二叉树转化为累加树

LeetCode(669)修剪二叉搜索树
题目
在这里插入图片描述

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        //注意是二叉搜索树,一定要按二叉搜索树的规则来做
        //采用先序递归的方法来做
        //判断终止条件-----返回为null
        if(root==null){
            return null;
        }
        //判断树的节点是否在区间里面,若树的节点不在区间则进行删除-----根节点被删除的情况,判断左右子树的保留情况
        if(root.val<low){//仅会出现一种情况
            //那么此时这颗以root为根树的左子树一定不保留,右子树可能保留,也可能不保留,需要对右子树进行判断
            TreeNode right=trimBST(root.right, low, high);
            return right;//此时直接将右子树判断的结果返回----直接返回,后面能接住
        }
        if(root.val>high){//进入之后直接把左节点返回回去了,相当于把节点直接删除了
            //那么此时这颗树的右子树一定不保留,左子树可能保留,需要对左子树进行判断
            TreeNode left=trimBST(root.left, low, high);
            return left;
        }
        //递归程序开始,采用先序遍历,采用根左右的方法
        root.left=trimBST(root.left, low, high);//左边树处理后返回根节点
        root.right=trimBST(root.right, low, high);//右边树处理后返回根节点
        return root;

    }
}

LeetCode(108)将有序数组转换为二叉搜索树
题目
在这里插入图片描述

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        //构造平衡二叉树-------思路,主要是切割区间----注意切割区间的终止条件
        //定义一个新的构建二叉树的方法,用于构建新的二叉树
        int left=0;//定义左参数,左区间
        int right=nums.length-1;
        TreeNode root=buildTreeNode(nums,left,right);
        return root;
    }
    //定义构建平衡二叉树的方法
    public TreeNode buildTreeNode(int[] nums,int left,int right){
        //采用左闭右闭的方法
        //判断终止条件-----即为构建不了二叉树的方法
        if(left>right){
            return null;
        }
        //单次递归的执行策略
        int mid=(left+right)/2;
        TreeNode root=new TreeNode(nums[mid]);
        //递归----先序遍历---根左右
        root.left=buildTreeNode(nums, left, mid-1);//左子树
        root.right=buildTreeNode(nums, mid+1, right);//右子树
        return root;
    }
}

LeetCode(538)把二叉树转化为累加树
题目
在这里插入图片描述

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int pre=0;
    public TreeNode convertBST(TreeNode root) {
        //回顾一下数组的操作方法,双指针
        //本题主要是更新节点的值
        updateTreeNodeVal(root);//将树的根节点传入进去
        //更新完成之后返回root
        return root;
    }
    public void updateTreeNodeVal(TreeNode root){
        //终止条件
        if(root==null){
            return;
        }
       
        updateTreeNodeVal(root.right);
        //中间节点的处理逻辑
        //此时到了最后一个节点值
        root.val=root.val+pre;//此时记录的是当前节点值
        pre=root.val;//要理解清楚,不要绕进去
        //第一个更新的是最右边-根-左
        updateTreeNodeVal(root.left);
    }
}

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

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

相关文章

数据安全之路:深入了解MySQL的行锁与表锁机制

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 数据安全之路&#xff1a;深入了解MySQL的行锁与表锁机制 前言基础innodb中锁与索引的关系如何避免表锁 前言 在当今数据密集的应用中&#xff0c;数据库锁成为了确保数据一致性和并发操作的关键工具…

Linux字符设备驱动中同类型多设备节点的创建---一个驱动程序支持多个同类型设备

文章目录 前言1 代码解析1.1 驱动层1.2 应用层 2 运行结果总结 前言 本期分享的内容相对比较简单&#xff0c;那就是同时注册多个同类型的字符设备驱动&#xff0c;那么这样我们就可以同时支持多个同类型的设备了&#xff01;下面来带大家看一下&#xff1a; 1 代码解析 1.1 …

【Flink精讲】Flink性能调优:内存调优

内存调优 内存模型 JVM 特定内存 JVM 本身使用的内存&#xff0c;包含 JVM 的 metaspace 和 over-head 1&#xff09; JVM metaspace&#xff1a; JVM 元空间 taskmanager.memory.jvm-metaspace.size&#xff0c;默认 256mb 2&#xff09; JVM over-head 执行开销&#xff1…

深入探讨基于大语言模型的数据标注

文章地址&#xff1a; https://arxiv.org/pdf/2402.13446 数据标注是将原始数据用相关信息进行标注&#xff0c;对于提高机器学习模型的效果至关重要。然而&#xff0c;这一过程往往需要大量人力和资金支持。先进大语言模型&#xff08;LLMs&#xff09;的出现&#xff0c;例如…

小程序--事件处理

一、事件对象 给小程序的事件传递参数&#xff0c;有以下两种方法&#xff1a; 1、自定义属性 <view class"item" wx:for"{{ 5 }}" wx:key"*this" data-index"{{index}}" bind:tap"onClick"></view> Page({o…

spss常用检验方法

spss常用检验方法 1 数据是否符合正态分布1.1符合正态分布1.1.1怎样的数据符合正态分布1.1.2 spss怎么统计正态分布1.1.3 方差齐性检验1.1.4 具体统计学分析 1.2 不符合正态分布1.2.1 Mann-Whitney U检验1.2.2 Wilcoxon符号秩检验1.2.3 Kruskal-Wallis H检验1.2.4 Friedman检验…

CCF-CSP: 因子化简(100分)

第一次提交的时候90分&#xff0c;显示的超时&#xff0c;第一反应是难道有死循环? 检查一遍发现并没有&#xff0c;那就是真的超时了&#xff0c;然后翻阅blog,发现不需要去做判断是否是素数这一步&#xff0c;原因是任意一个非素数都是素数乘积构成&#xff0c;比如说&#…

提高移动应用的安全性:策略与实践

提高移动应用的安全性&#xff1a;策略与实践 随着移动应用的普及&#xff0c;安全性问题变得日益重要。用户数据保护、应用逻辑安全、以及防止恶意攻击都是开发者必须关注的重点。本文将探讨如何通过一系列策略和实践来提高移动应用的安全性。 1. 数据加密与保护 敏感数据加…

ABAP - Function ALV 05 添加选择框列、全选、取消全选

很多用户不习惯原生GRID的选择模式&#xff0c;所以业务需要用到自定义的选择框来进行数据的操作&#xff0c;显示效果如图所示&#xff0c;增加一条选择列&#xff0c;且配置全选和全选全选的按钮功能&#xff0c;如下图所示。 实现这种功能需要用到Fieldcat的参数控制以及GUI…

c#高级-正则表达式

正则表达式是由普通字符和元字符&#xff08;特殊符号&#xff09;组成的文字形式 应用场景 1.用于验证输入的邮箱是否合法。 2.用于验证输入的电话号码是否合法。 3.用于验证输入的身份证号码是否合法。等等 正则表达式常用的限定符总结&#xff1a; 几种常用的正则简写表达式…

力扣--动态规划1027.最长等差数列

思路分析&#xff1a; 使用动态规划的思想&#xff0c;定义二维数组dp&#xff0c;其中dp[i][j]表示以nums[i]为结尾&#xff0c;公差为(j-1000)的等差数列长度。为了适应负数的情况&#xff0c;将公差的范围设为[-1000, 1000]&#xff0c;并且加上1000作为数组索引。 初始化r…

javaApI(Application Programming Interface)应用程序编程接口

ApI概念 Apl:指的是官方给开发人员提供的说明文档&#xff0c;对语言中有哪些类&#xff0c;类中有哪些方法进行说明 Objict 类 java.lang.Object 是java类体系结构中最顶层的类 Object可以表示java中任意的类 Object类中的方法 toString() 输出一个对象&#xff0c;但是…

Python服务器监测测试策略与工具:确保应用的高可用性!

在构建高可用性的应用程序时&#xff0c;服务器监测测试是至关重要的一环。Python作为一种强大的编程语言&#xff0c;提供了丰富的工具和库来帮助我们进行服务器监测测试。本文将介绍一些关键的策略和工具&#xff0c;帮助你确保应用的高可用性。 1. 监测策略的制定&#xff…

matlab|基于DistFlow潮流的配电网故障重构(输入任意线路)

目录 1 主要内容 2 部分代码 3 程序结果 4 下载链接 1 主要内容 程序采用适用于辐射状网络的DistFlow潮流模型&#xff0c;可输入任意故障线路编号&#xff0c;得到优化重构结果。这个程序是配电网故障重构可视化matlabyalmip的升级版&#xff0c;原来的程序是以电压质量作…

介绍 PIL+IPython.display+mtcnn for 音视频读取、标注

1. nn.NLLLoss是如何计算误差的? nn.NLLLoss是负对数似然损失函数&#xff0c;用于多分类问题中。它的计算方式如下&#xff1a;首先&#xff0c;对于每个样本&#xff0c;我们需要将其预测结果通过softmax函数转换为概率分布。softmax函数可以将一个向量映射为一个概率分布&…

第四套CCF信息学奥赛c++ CSP-J认证初级组 中小学信奥赛入门组初赛考前模拟冲刺题(阅读程序题)

第四套中小学信息学奥赛CSP-J考前冲刺题 二、阅读程序题 (程序输入不超过数组或字符串定义的范围&#xff0c;判断题正确填√错误填X;除特殊说明外&#xff0c;判断题 1.5分&#xff0c;选择题3分&#xff0c;共计40分) 第一题 归并排序 1 #include <iostream> 2 usi…

【Java程序设计】【C00285】基于Springboot的游戏分享网站(有论文)

基于Springboot的游戏分享网站&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的游戏分享网站 本系统分为系统功能模块、管理员功能模块以及用户功能模块。 系统功能模块&#xff1a;在网站首页可以查看首页、游戏…

Linux环境基础开发工具使用篇(三) git 与 gdb

一、版本控制器-git 1.简单理解: ①git既是服务端&#xff0c;又是客户端 ②git会记录版本的变化 ③git是一个去中心化的分布式软件 git/gitee 是基于git仓库搭建的网站&#xff0c;让版本管理可视化 2.git 三板斧提交代码 查看安装的git版本 git--version 命令行提交代…

SpringMVC 学习(四)之获取请求参数

目录 1 通过 HttpServletRequest 获取请求参数 2 通过控制器方法的形参获取请求参数 3 通过 POJO 获取请求参数&#xff08;重点&#xff09; 1 通过 HttpServletRequest 获取请求参数 public String handler1(HttpServletRequest request) <form action"${pageCont…

Linux 文件操作

目录 C语言下的文件操作 Linux下的文件操作 文件描述符的前因后果 文件描述符的概念 文件描述符的分配规则 理解C语言的FILE结构体 Linux重定向 文件缓冲区 文件系统 文件系统的概念 ext2文件系统 对ext2的补充 虚拟文件系统的概念 软硬链接 C语言下的文件操作 …