代码随想录打卡第十八天

代码随想录–二叉树部分

day 17 休息日
day 18 二叉树第五天


文章目录

  • 代码随想录--二叉树部分
  • 一、力扣654--最大二叉树
  • 二、力扣617--合并二叉树
  • 三、力扣700--二乘树中的搜素
  • 四、力扣98--验证二叉搜索树


一、力扣654–最大二叉树

代码随想录题目链接:代码随想录

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点,其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

题目已经把思路写出来了,正常找最大值下标然后分割数组就行,和构建二叉树一模一样

代码如下:

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.empty()) return nullptr;int maxIndex = 0;for(int i = 0; i < nums.size(); i ++){if(nums[i] > nums[maxIndex]) maxIndex = i;}vector<int> leftTreeNums(nums.begin(), nums.begin() + maxIndex);vector<int> rightTreeNums(nums.begin() + maxIndex + 1, nums.end());TreeNode * curr = new TreeNode(nums[maxIndex]);curr->left = constructMaximumBinaryTree(leftTreeNums);curr->right = constructMaximumBinaryTree(rightTreeNums);return curr;}
};

二、力扣617–合并二叉树

代码随想录题目链接:代码随想录

给你两棵二叉树: root1 和 root2 。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。

思路比较清楚,用递归,每次传入root1和root2,那就对他们比较:
1、如果有一个为空而另一个不为空,说明后面都不用合并了,空树和非空树合并,结果就是非空树本身
2、如果两个都为空,那么返回空树,0+0=0,很合理的
3、如果两个都不为空,那么把val加起来放给root1,并且让root1的左右子树继续递归合并即可

代码如下:

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(!root1 && !root2) return nullptr;if(!root1 && root2) return root2;if(!root2 && root1) return root1;root1->val += root2->val;root1->left = mergeTrees(root1->left, root2->left);root1->right = mergeTrees(root1->right, root2->right);return root1;}
};

三、力扣700–二乘树中的搜素

代码随想录题目链接:代码随想录

给定二叉搜索树(BST)的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。

本题就是对二叉搜索树的模拟使用,二叉搜索树意思是左节点值<中节点值<右节点值的树

代码如下:

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(!root) return nullptr;if(root->val > val) return searchBST(root->left, val);else if(root->val < val) return searchBST(root->right, val);else return root;}
};

四、力扣98–验证二叉搜索树

代码随想录题目链接:代码随想录

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

这个题不能单纯地比较节点数字大小,因为有可能存在这种情况:
在这里插入图片描述
所以要对这个树进行整体地判断,而不能一颗一颗去判断,可能子树是二叉搜索树,但是整个树就不是了

而注意到,如果这个树是二叉搜索树,那么它的中序遍历一定是递增的,所以只要进行一个中序遍历,再进行递增判断即可

代码如下:

class Solution {
public:void traversal(TreeNode * root, vector<int> & path){if(!root) return;traversal(root->left, path);path.push_back(root->val);traversal(root->right, path);}bool isValidBST(TreeNode* root) {vector<int> path;traversal(root, path);for(int i = 1; i < path.size(); i ++){if(path[i]<=path[i - 1]) return false;}return true;}
};

写的时候还忘了递归中序遍历的写法了,补上模板:

    void trans(TreeNode* curr, vector<int> & result){if(curr == nullptr) return;trans(curr->left, result);       // 左result.push_back(curr->val);     // 中trans(curr->right, result);      // 右}// 根据前中后序遍历分别改为:中左右、左中右、左右中的顺序即可

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

美容师有什么话术技巧?美业人如何提升自己的销售技巧?博弈美业门店管理系统分享经验

作为一名美容师&#xff0c;有一些话术和销售技巧可以帮助你提升服务质量和销售业绩。以下是博弈美业收银系统分享的一些建议&#xff1a; 1.建立信任&#xff1a; 在与客户交流时&#xff0c;表现出真诚、友好和专业的态度。倾听客户的需求&#xff0c;并给予针对性的建议&a…

随笔(一)

1.即时通信软件原理&#xff08;发展&#xff09; 即时通信软件实现原理_即时通讯原理-CSDN博客 笔记&#xff1a; 2.泛洪算法&#xff1a; 算法介绍 | 泛洪算法&#xff08;Flood fill Algorithm&#xff09;-CSDN博客 漫水填充算法实现最常见有四邻域像素填充法&#xf…

Redis代替Session实现共享

集群的session共享问题 session共享问题&#xff1a;多台tomcat并不共享session存储空间&#xff0c;当请求切换到不同的tomcat服务时导致数据丢失的问题。 session的替代方案&#xff1a; 数据共享内存存储key、value结构 将redis替换session可以解决session共享问题

Day65 代码随想录打卡|回溯算法篇---组合总和II

题目&#xff08;leecode T40&#xff09;&#xff1a; 给定一个候选人编号的集合 candidates 和一个目标数 target &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意&#xff1a;解集不能包含…

第十八节 LLaVA如何按需构建LORA训练(视觉、语言、映射多个组合训练)

文章目录 前言一、基于llava源码构建新的参数1、添加lora_vit参数2、训练命令脚本设置二、修改源码,构建lora训练1、修改源码-lora训练2、LLM模型lora加载3、VIT模型加载4、权重冻结操作5、结果显示三、实验结果前言 如果看了我前面文章,想必你基本对整个代码有了更深认识。…

DevOps实战:使用GitLab+Jenkins+Kubernetes(k8s)建立CI_CD解决方案

一.系统环境 本文主要基于Kubernetes1.21.9和Linux操作系统CentOS7.4。 服务器版本docker软件版本Kubernetes(k8s)集群版本CPU架构CentOS Linux release 7.4.1708 (Core)Docker version 20.10.12v1.21.9x86_64CI/CD解决方案架构图:CI/CD解决方案架构图描述:程序员写好代码之…

学习数据库2

在数据库中创建一个表student&#xff0c;用于存储学生信息 查看建表结果 向student表中添加一条新记录 记录中id字段的值为1&#xff0c;name字段的值为"monkey"&#xff0c;grade字段的值为98.5 并查看结果 向student表中添加多条新记录 2,"bob"…

算法之工程化内容(2)—— Git常用命令

目录 1. git初始化配置 2. 新建仓库 3. 工作区——>暂存区——>本地仓库 4. git reset回退版本 5. 查看差异 git diff 6. 删除文件git rm 7. .gitignore 8. vscode操作git 9. git分支、合并和删除 10. 解决合并冲突 11. 回退和rebase 12. 添加远程仓库 参考链接&#xff…

用于视频生成的扩散模型

学习自https://lilianweng.github.io/posts/2024-04-12-diffusion-video/ 文章目录 3D UNet和DiTVDMImagen VideoSora 调整图像模型生成视频Make-A-Video&#xff08;对视频数据微调&#xff09;Tune-A-VideoGen-1视频 LDMSVD稳定视频扩散 免训练Text2Video-ZeroControlVideo 参…

C++deque容器

文章目录 deque容器概念deque操作deque对象的带参数构造deque头部和末尾的添加移除操作deque的数据存取deque与迭代器deque赋值deque插入deque删除 deque容器概念 deque是双端数组&#xff0c;而vector是单端的。 deque头部和尾部添加或移除元素都非常快速, 但是在中部安插元…

一个php文件怎么实现联系表单自动发送邮件

学习PHP&#xff1a;如何编写一个自动发送邮件的联系表单处理器&#xff1f; 无论是反馈意见、业务咨询&#xff0c;还是技术支持&#xff0c;联系表单都能为用户提供便捷的交流途径。AokSend将探讨如何通过一个PHP文件实现联系表单的自动发送邮件功能。 php文件&#xff1a;…

Java实战:寻找完美数

文章目录 一、何谓完美数二、寻找完美数&#xff08;一&#xff09;编程思路&#xff08;二&#xff09;编写程序&#xff08;三&#xff09;运行程序 三、实战小结 一、何谓完美数 完美数是一种特殊的自然数&#xff0c;它等于其所有正除数&#xff08;不包括其本身&#xff…

数据结构作业/2024/7/9

2>实现双向循环链表的创建、判空、尾插、遍历、尾删、销毁 fun.c #include "head.h" //1.双向循环链表的创建 doubleloop_ptr create_list() …

数据结构——顺序表【C】

顺序表 1. 顺序表的概念以及结构1.1概念1.2静态顺序表和动态顺序表 2. 顺序表接口模拟实现接口总览2.1 初始化数据和销毁容器 2.2 顺序表的尾插和尾删2.3 头插和头删2.4 任意位置插入和删除数据2.5 查找数据 3. 顺序表的问题 &#xff1a; 1. 顺序表的概念以及结构 1.1概念 顺…

利用亚马逊云科技云原生Serverless代码托管服务开发OpenAI ChatGPT-4o应用

今天小李哥继续介绍国际上主流云计算平台亚马逊云科技AWS上的热门生成式AI应用开发架构。上次小李哥分享​了利用谷歌云serverless代码托管服务Cloud Functions构建Gemini Pro API​&#xff0c;这次我将介绍如何利用亚马逊的云原生服务Lambda调用OpenAI的最新模型ChatGPT 4o。…

初识SpringBoot

1.Maven Maven是⼀个项⽬管理⼯具, 通过pom.xml⽂件的配置获取jar包&#xff0c;⽽不⽤⼿动去添加jar包 主要功能 项⽬构建管理依赖 构建Maven项目 1.1项目构建 Maven 提供了标准的,跨平台(Linux, Windows, MacOS等)的⾃动化项⽬构建⽅式 当我们开发了⼀个项⽬之后, 代…

LLM指令微调Prompt的最佳实践(六):基于ChatGPT搭建聊天机器人

文章目录 1. 前言2. Prompt定义3. 搭建聊天机器人Chatbot3.1 角色定义1. system2. assistant3. user4. 总结 3.2 初始函数3.3 讲笑话机器人3.4 订餐机器人 4. 参考 1. 前言 前情提要&#xff1a; 《LLM指令微调Prompt的最佳实践&#xff08;一&#xff09;&#xff1a;Prompt原…

Apache AGE 安装部署

AGE概述 概述 我们可以通过源码安装、拉取docker镜像运行、直接使用公有云三种方式中的任意一种来使用Apache AGE 获取 AGE 发布版本 可以在 https://github.com/apache/age/releases 找到发布版本和发布说明。 源代码 源代码可以在 https://github.com/apache/age 找到…

万字长文整理Java多线程相关面试题

目录 ​1. 什么是线程和进程&#xff1f; 线程与进程有什么区别&#xff1f; 那什么是上下文切换&#xff1f; 进程间怎么通信&#xff1f; 什么是用户线程和守护线程&#xff1f; 2. 并行和并发的区别&#xff1f; 3. 创建线程的几种方式&#xff1f; Runnable接口和C…

Codeforces Round 954 (Div. 3) F. Non-academic Problem

思路&#xff1a;考虑缩点&#xff0c;因为是无向图&#xff0c;所以双连通分量缩完点后是一棵树&#xff0c;我们去枚举删除每一条树边的答案&#xff0c;然后取最小值即可。 #include <bits/stdc.h>using namespace std; const int N 3e5 5; typedef long long ll; …