当前位置: 首页 > news >正文

代码随想录day20 开始二叉搜索树

654.最大二叉树

题目

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:

  • 二叉树的根是数组中的最大元素。
  • 左子树是通过数组中最大值左边部分构造出的最大二叉树。
  • 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树,并且输出这个树的根节点。

示例 :

654.最大二叉树

思考

本题也是通过递归的方式构造二叉树:找到数组中最大的数,然后最大数左部分变成一个数组,右部分变成一个数组,继续node->left、node->right递归两个数组,注意创建左右数组的时候需要跳过node

代码

class Solution {

public:

    TreeNode* traversal(vector<int>& nums) {

        if(nums.size() == 0) return nullptr;

        int maxValue = INT_MIN;

        for(auto i : nums) {

            maxValue = max(maxValue, i);

        }

        TreeNode* node = new TreeNode(maxValue);

        int pos = 0;

        for(; pos < nums.size(); pos++) {

            if(nums[pos] == maxValue) break;

        }

        vector<int> left(nums.begin(), nums.begin() + pos);

        vector<int> right(nums.begin() + pos + 1, nums.end());

        node->left = traversal(left);

        node->right = traversal(right);

        return node;

    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

        return traversal(nums);

    }

};

617.合并二叉树

题目

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

617.合并二叉树

注意: 合并必须从两个树的根节点开始。

思考

想了很久怎么用层序遍历做,卡在了如果tree1和tree2的层数不一样该怎么遍历,看了解题答案发现其实就是把tree1和tree2的两个结点都存入que即可,同时并不需要计算size,因为可以用tree1来代替new TreeNode,这里需要判断四个情况,node1->left != nullptr && node2->left != nullptr、node1->right != nullptr && node2->right != nullptr、node1->left == nullptr && node2->left != nullptr、node1->right == nullptr && node2->right != nullptr。

代码

class Solution {

public:

    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {

        if(root1 == nullptr) return root2;

        if(root2 == nullptr) return root1;

        queue<TreeNode*> que;

        que.push(root1);

        que.push(root2);

        while(!que.empty()) {

            TreeNode* node1 = que.front();

            que.pop();

            TreeNode* node2 = que.front();

            que.pop();

            node1->val += node2->val;

            if(node1->left != nullptr && node2->left != nullptr) {

                que.push(node1->left);

                que.push(node2->left);

            }

            if(node1->right != nullptr && node2->right != nullptr) {

                que.push(node1->right);

                que.push(node2->right);                    

            }

            if(node1->left == nullptr && node2->left != nullptr) node1->left = node2->left;

            if(node1->right == nullptr && node2->right != nullptr) node1->right = node2->right;

            }

        return root1;

    }  

};

700.二叉搜索树中的搜索

题目

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

例如,

700.二叉搜索树中的搜索

在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。

思考

开始二叉搜索树啦,其实二叉搜索树定义很简单,一个结点的左子树所有结点都比它小,右子树的所有结点都比它大,本题其实就是找到一个二叉搜索树的子树,如果这个结点大于给定val,那么root = root->right,如果小于,那么root = root->left,如果等于就return root; 注意这里要用while(root != null)来做循环持续判断root

代码

class Solution {

public:

    TreeNode* searchBST(TreeNode* root, int val) {

        while(root != NULL) {

            if(root->val > val) root = root->left;

            else if(root->val < val) root = root-> right;

            else return root;

        }

        return NULL;

    }

};

98.验证二叉搜索树

题目

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

98.验证二叉搜索树

思考

这题陷入了一个常见的误区,就是没有判断该结点左右子树的所有元素都小于或大于该结点,而仅仅判断了该结点的左右结点,看了卡哥的视频,才发现二叉搜索树需要用中序遍历来写:

1、用中序遍历来将二叉树变成一个数组,然后判断这个数组是不是递增排布的

2、创建一个值为最小值的maxValue,用中序遍历来将每一个结点都与maxValue进行判断,如果大于它,那么mavValue的值就被该结点的值取代,如果小于,就return false,因为二叉搜索树左中右是递增关系

代码

class Solution {

public:

    long long maxValue = LONG_MIN;

    bool isValidBST(TreeNode* root) {

        if(root == nullptr) return true;

        bool left = isValidBST(root->left);

        if(root->val > maxValue) maxValue = root->val;

        else return false;

        bool right = isValidBST(root->right);

        return left && right;

    }

};

相关文章:

代码随想录day20 开始二叉搜索树

654.最大二叉树 题目 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下&#xff1a; 二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构…...

从0开始python学习-39.requsts库

目录 HTTP协议 1. 请求 2. 响应 Requests库 1. 安装 2. 请求方式 2.1 requests.请求方式(参数) 2.2 requests.request() 2.3 requests.session().request() 2.4 三种方式之间的关联 3. 请求参数 3.1 params&#xff1a;查询字符串参数 3.2 data&#xff1a;Form表单…...

【面试高频算法解析】算法练习3 双指针

前言 本专栏旨在通过分类学习算法&#xff0c;使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目&#xff0c;帮助您深度理解每种算法&#xff0c;避免出现刷了很多算法题&#xff0c;还是一知半解的状态 专栏导航 二分查找回溯双指针滑动窗口深度优先搜索…...

React16源码: Why16, 研究源码的意义, 源码目录核心结构分析

为什么要选择React16 现在React18都早已实践很多&#xff0c;为何回过头来看16版本的代码理由如下 从实际出发&#xff0c;企业内老旧项目多为16版本&#xff0c;理解16的核心能够帮助我们快速解决问题16版本React是完全重写了核心代码, 是一次重大的更新 引入了 fiber 这个概…...

mybatis-flex笔记

MyBatis-Flex 的增删改功能 - MyBatis-Flex 官方网站https://mybatis-flex.com/zh/base/add-delete-update.html 代码https://gitee.com/hntianshu/mybatis-flex-test 一 新增数据 不忽略 null 值。 就是允许有null 忽略null 就是不允许有null BaseMapper 的接口提供了 inser…...

Debezium发布历史47

原文地址&#xff1a; https://debezium.io/blog/2019/02/13/debezium-0-9-1-final-released/ 欢迎关注留言&#xff0c;我是收集整理小能手&#xff0c;工具翻译&#xff0c;仅供参考&#xff0c;笔芯笔芯. Debezium 0.9.1.Final 发布 二月 13, 2019 作者&#xff1a; Gunna…...

Python爬虫抓包常见问题解决

对于Python爬虫和Fiddler抓包&#xff0c;可能遇到的问题及解决&#xff1a; 代理设置错误&#xff1a;如果你在使用Python爬虫时遇到抓不到包的问题&#xff0c;首先应该检查你的浏览器代理设置是否正确。以Chrome为例&#xff0c;代理设置为&#xff1a;右上角菜单按钮>设…...

c++跨平台ui

fltk https://gitee.com/mirrors_fltk/fltk.git codeblock中有fltk项目开发模板,可以快速构建项目 wxwidget https://gitee.com/sofu456/wxWidgets.git git submodule update --init --recursive 打开demo和sample set(wxBUILD_SAMPLES ALL) set(wxBUILD_DEMOS ON) build/…...

stable diffusion 基础教程-提示词之艺术风格用法

展现夕阳 golden hour, (rim lighting):1.2, warm tones, sun flare, soft shadows, vibrant colors, hazy glow, painterly effect, dreamy atmosphere阴影 chiaroscuro, (high contrast):1.2, dramatic shadows, bold highlights, moody atmosphere, captivating inte…...

【日积月累】Java中 正则表达式

目录 日积月累】Java中 正则表达式 1.前言2.基本语法3.Pattern和Matcher类4.校验的表达式大全5.参考文章所属专区 日积月累 1.前言 正则表达式是一种用于匹配文本模式的语法,它通常与编程语言一起使用。在Java中,正则表达式用于匹配字符串,可以使用Pattern和Matcher类来实…...

Java调用百度云语音识别【音频转写】

百度云文档 ttps://ai.baidu.com/ai-doc/SPEECH/Bk5difx01 示例代码: import com.alibaba.fastjson.JSON; import com.alibaba.fastjson.JSONArray; import lombok.extern.slf4j.Slf4j; import okhttp3.*; import org.json.JSONObject; import org.springframework.stereotyp…...

pyparamvalidate 项目背景和需求分析

目录 一、前置说明1、总体目录2、本节目标 二、项目背景三、需求分析三、后置说明1、要点小结2、下节预告 一、前置说明 1、总体目录 《 pyparamvalidate 参数校验器&#xff0c;从编码到发布全过程》 2、本节目标 阐述 pyparamvalidate 项目背景和需求分析。 二、项目背景…...

Docker Linux快速安装及Nginx部署

前言 最近正在部署一套新的Linux服务器环境&#xff0c;基于Docker来部署所有的应用&#xff0c;顺便整理了一套经过验证的操作手册&#xff0c;以便大家遇到类似需求时&#xff0c;可以直接拿来用。 本文会涉及以下知识点&#xff1a;Docker的Linux安装和卸载、Docker用户组…...

Mac M1 Parallels CentOS7.9 Install Parallels Tools

一、挂载parallels-tools安装包 mkdir /media/cdrom/ mount /dev/cdrom /media/cdrom/ mount: /dev/sr0 写保护&#xff0c;将以只读方式挂载二、GCC升级 yum install -y centos-release-scl yum install -y devtoolset-8-gcc*# 切换当前会话中gcc版本为8 scl enable devtool…...

计算机网络物理层 习题答案及解析

2-1 下列选项中&#xff0c;不属于物理层接口规范定义范畴的是&#xff08; D &#xff09;。 A. 引脚功能 B. 接口形状 C. 信号电平 D. 传输媒体 【答案】D 【解析】 2-2 某网络在物理层规定&#xff0c;信号的电平范围为- 15V~15V &#xff0c; 电线长…...

【解决】Unity 设置跨设备分辨率表现

开发平台&#xff1a;Unity 2018版本以上 开发语言&#xff1a;CSharp 编程平台&#xff1a;Visual Studio 2022   问题描述 使用 UnityEngine.dll 中关于设置分辨率的方法时&#xff0c;无法满足应用以设定分辨率进行屏幕显示问题。因而造成画面不同程度的拉伸情况。而这种情…...

基于单片机的智能衣柜设计

一、摘要 随着科技的不断发展&#xff0c;人们对于生活品质的要求越来越高。智能衣柜作为智能家居的一个重要组成部分&#xff0c;能够为用户提供便捷、个性化的衣物管理服务。本文主要研究了基于单片机的智能衣柜设计&#xff0c;通过对硬件系统和软件系统的设计与实现&#…...

HttpSession的使用

1 HttpSession 概述 在 Java Servlet API 中引入 session 机制来跟踪客户的状态。session 指的是在一段时间内&#xff0c;单个客户与 Web 服务器的一连串相关的交互过程。在一个 session 中&#xff0c;客户可能会多次请求访问同一个网页&#xff0c;也有可能请求访问各种不同…...

人工智能在金融领域的应用存在的4大挑战

金融服务供应商应该有计划地应对AI面临的难题 金融行业投资人工智能热潮带来有关数据安全和透明度的新问题。由于数据管理实践随着新的 AI 解决方案的引入而不断发展&#xff0c;应对这些新问题以及金融服务领域 AI 面临的其他挑战尤为重要。各组织必须认识到可能面临以下挑战…...

EasyExcel写出包含多个sheet页的Excel

https://blog.csdn.net/qq_38751895/article/details/131852740...

分类预测 | Matlab实现RP-CNN-LSTM-Attention递归图优化卷积长短期记忆神经网络注意力机制的数据分类预测【24年新算法】

分类预测 | Matlab实现RP-CNN-LSTM-Attention递归图优化卷积长短期记忆神经网络注意力机制的数据分类预测【24年新算法】 目录 分类预测 | Matlab实现RP-CNN-LSTM-Attention递归图优化卷积长短期记忆神经网络注意力机制的数据分类预测【24年新算法】分类效果基本描述模型描述程…...

【教学类-09-04】20240102《游戏棋N*N》数字填写,制作棋子和骰子

作品展示 背景需求&#xff1a; 最近在清理学具材料库&#xff0c;找到一套1年多前的《N*N游戏棋》&#xff0c;把没有用完的棋盘拿出来&#xff0c;&#xff0c;想给大4班换花样&#xff0c;并把它们用掉。 程序代码在这里 【教学类-09-03】20221120《游戏棋10*10数字如何直接…...

【flink番外篇】9、Flink Table API 支持的操作示例(14)- 时态表的join(java版本)

Flink 系列文章 一、Flink 专栏 Flink 专栏系统介绍某一知识点&#xff0c;并辅以具体的示例进行说明。 1、Flink 部署系列 本部分介绍Flink的部署、配置相关基础内容。 2、Flink基础系列 本部分介绍Flink 的基础部分&#xff0c;比如术语、架构、编程模型、编程指南、基本的…...

【leetcode100-30】【链表】两两交换链表节点

【题干】 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&#xff09;。 【思路】 先说递归的&#xff0c;退出条件很明显&#xff0c;当剩…...

小秋SLAM入门实战ubuntu所有文章汇总

Ubuntu系统安装详细教程 Ubuntu系统安装ROS详细教程 Ubuntu系统下如何搭建深度学习和SLAM开发环境 Ubuntu系统搭建SLAM开发环境 ubuntu 终端如何停止快速打印的输出以及恢复命令 ubuntu 终端如何快速打开当前路径下的图形化窗口界面&#xff1f; killall -9用途用法 ps -xu | …...

深度学习课程实验二深层神经网络搭建及优化

一、 实验目的 1、学会训练和搭建深层神经网络&#xff1b; 2、掌握超参数调试正则化及优化。 二、 实验步骤 初始化 1、导入所需要的库 2、搭建神经网络模型 3、零初始化 4、随机初始化 5、He初始化 6、总结三种不同类型的初始化 正则化 1、导入所需要的库 2、使用非正则化…...

Elasticsearch:Serarch tutorial - 使用 Python 进行搜索 (二)

这个是继上一篇文章 “Elasticsearch&#xff1a;Serarch tutorial - 使用 Python 进行搜索 &#xff08;一&#xff09;” 的续篇。在今天的文章中&#xff0c;我们接着来完成如何进行分页及过滤。 分页 - pagination 应用程序处理大量结果通常是不切实际的。 因此&#xff0…...

力扣labuladong——一刷day84

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣743. 网络延迟时间 前言 Dijkstra 算法&#xff08;一般音译成迪杰斯特拉算法&#xff09;无非就是一个 BFS 算法的加强版&#xff0c;它们都是从二叉…...

Linux环境vscode clang-format格式化:vscode clang format command is not available

问题现象 vscode安装了clang-format插件&#xff0c;但是使用就报错 问题原因 设置中配置的clang-format插件工具路径不正确。 解决方案 确认本地安装了clang-format工具&#xff1a;终端输入clang-format&#xff08;也可能是clang-format-13等版本&#xff0c;建议tab自…...

【KingbaseES】实现MySql函数WEEKS_BETWEEN

WEEKS_BETWEEN CREATE OR REPLACE FUNCTION weeks_between(start_date date, end_date date) RETURNS integer AS $$ BEGIN RETURN EXTRACT(WEEK FROM end_date) - EXTRACT(WEEK FROM start_date); END; $$ LANGUAGE plpgsql IMMUTABLE;结果展示...

建设与管理局网站/sem竞价代运营

1.常用事件 onload&#xff1a;当页面中的所有的标签&#xff0c;文档&#xff0c;图片等资源加载完毕后会触发onload事件      onclick&#xff1a;鼠标单击事件      ondblclick&#xff1a;鼠标双击事件      onmousedown&#xff1a;鼠标按下事件    …...

深圳 德 网站建设/陕西网站关键词自然排名优化

严格模式是es5之后新增的。 ie10以上的版本才支持这种严格模式。...

做外贸哪些网站可以发免费信息/百度文库个人登录

set 不允许重复 无序 hashset->hashmap LinkedHashSet—LinkedHashMap TreeSet----TreeMap实现了SortedSet接口 return map.put(e, PRESENT)null; //PRESENT始终是一个new object 将元素作为key存储&#xff0c;这也是为什么Set元素无序&#xff0c;不重复&#xff0c;不为n…...

西安网站建设huanxi/教育培训网站模板

在使用3dmax 9.0时&#xff0c;导入Illustrator文件时提示"Line in file exceeds 255 characters"&#xff08;之前8.0也有同样的问题&#xff09;引起这个问题的原因是Illustrator CS(V 11.0) 和 CS2(V 12.0) 存储 .ai 文件使用的是一种“不断行”的存储方式&#x…...

主流网站/seo教程视频

OS : Ubuntu 18.04.1 LTSDBMS : mysql 8.0.12typesetting : Markdown数据&#xff0c;数据&#xff0c;命根就在数据 ! 操作数据库时&#xff0c;一定要谨慎小心。师万物 的代码看看就好&#xff0c;要有自己的判断。遇到抉择&#xff0c;要不耻上下问。examplestuUbuntu:~$ my…...

塑料机械怎么做网站/企业管理咨询培训

常用的负载均衡技术比较DNS 轮询DNS本身的机制不再赘述&#xff0c;这里主要看一看基于DNS的负载均衡&#xff0c;其大致原理很清楚&#xff0c;DNS系统本身支持同一个域名映射到多个ip (A记录&#xff09;,例如 这样每次向DNS系统询问该域名的ip地址时&#xff08;Tell Me The…...