Leetcoder Day17| 二叉树 part06

语言:Java/C++ 

654.最大二叉树

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

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

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

示例 :

题目中说了输入的数组大小一定是大于等于1的,所以我们不用考虑小于1的情况,那么当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。那么应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。

随后找当前整个数组的最大值,根据最大值的下标将数组分为左子树和右子树,继续递归进行构建。

class Solution {TreeNode traversal(int[] nums, int left, int right){if(right <= left ) return null;  //判空if(right-left==1){ //判断是否为一个节点,左闭右开return new TreeNode(nums[left]);}int maxIdx=left;int maxValue=nums[left];for(int i=left+1;i<right;i++){if(nums[i]>maxValue){maxValue=nums[i];maxIdx=i;}}TreeNode node = new TreeNode(maxValue);node.left=traversal(nums, left, maxIdx);node.right=traversal(nums, maxIdx+1, right);return node;}public TreeNode constructMaximumBinaryTree(int[] nums) {return traversal(nums, 0, nums.length);}   
}

617.合并二叉树 617.合并二叉树 

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

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

这道题我的第一个想法是建立一个哈希表,层次遍历并存储第一个树的位置和值,如果该位置没有节点则为-1,随后创建新的节点,遍历第二个树,若当前位置已经有节点,则将两个节点值相加返回;如果第二棵树没有节点,但第一棵树有,则直接返回第一棵树的值;如果第一棵树没有节点,则直接返回第二棵树的值;若第二棵树的节点数少于第一棵树,则在遍历完第二棵树后直接将第一棵树的剩余节点返回。但是这个思路无疑增加了很多复杂性,其实遍历两棵树和遍历一棵树的思路是一样的,采用前序遍历即可。

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null && root2!=null) return root2; if(root2==null && root1!=null) return root1; if (root1 == null && root2 == null) return null;TreeNode root=new TreeNode(root1.val+root2.val);root.left=mergeTrees(root1.left,root2.left);root.right=mergeTrees(root1.right, root2.right);return root;}
}

700.二叉搜索树中的搜索

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

例如,

因为本文的题设是二叉搜索树,所以这题就相对好办了,二叉搜索树是有序树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉搜索树

因此,找到值等于val的点然后递归返回从这个点以后的树即可:

class Solution {TreeNode traversal(TreeNode root, int val){if(root==null||root.val==val) return root;if(root.val>val){return traversal(root.left, val);}else{return traversal(root.right, val);}}public TreeNode searchBST(TreeNode root, int val) {return traversal(root, val);}
}

98.验证二叉搜索树

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

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

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

考研时数据结构里有一个结论:中序遍历下,输出的二叉搜索树节点的数值是有序序列,因此可以先将树转换为列表或数组,再判断是否有序即可。注意在Java中,如果将树转换为列表List,则需要用.get和size()来获取列表的值和长度,如果是数组,因为不知道树的节点个数,所以需要先设置一个很大的值,所以也可以先将树转换为列表,再将列表转换为数组。

class Solution {public void traversal(TreeNode root, List<Integer> vec){if(root==null) return;traversal(root.left, vec);vec.add(root.val);traversal(root.right, vec);}public boolean isValidBST(TreeNode root) {List<Integer> res=new ArrayList<Integer>();traversal(root, res); // 将列表转换为数组Integer[] arr=res.toArray(new Integer[res.size()]);  for(int i=1; i<arr.length;i++){if(arr[i]<=arr[i-1]) {return false; }}return true;}
}

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

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

相关文章

PLC设置网口通讯的原因

PLC设置网口通讯功能&#xff0c;是现场总线向工业以太网的迈进&#xff0c;更是为了在网口之上构建更为庞大、开放的大一统的生态系统。 有了以太网&#xff0c;特别是TCP/IP协议后&#xff0c;全员工控人的日常工作更为便利了。 主要体现在以下4点&#xff1a; 1.再也不需要…

linux逻辑卷/dev/mapper/centos-root扩容增加空间

centos7中/dev/mapper/centos-root扩容 问题文件系统根目录&#xff0c;/dev/mapper/centos-root空间满了&#xff0c;导致k8s不停重启 1.查看磁盘情况 df -h #查看最大占用目录 du -h -x --max-depth12.查看磁盘信息 fdisk -l3.查看磁盘分区层级 lsblk可见剩余空闲60G空间…

Visual Paradigm 工具使用思考

大型项目的管理与实施&#xff0c;需要有高效的管理工具&#xff0c;VP算是不错的&#xff0c;美中不足是界面太死板&#xff0c;使用不便利&#xff0c;对于小型项目按照这个模式来&#xff0c;相当麻烦。 当然肯定会有人觉得不错&#xff0c;需要的&#xff0c;联系我

nacos集群部署

一 部署mysql 根据下面文章 docker安装mysql和数据挂载_docker run -p 3306:3306 -name mysql -v /mydata/mys-CSDN博客 建议&#xff1a;使用Mysql5.7&#xff0c;之前尝试使用Mysql8.0&#xff0c;会报错 经过查询&#xff1a; 报错原因 可能是数据库版本过高 二 部署na…

蓝桥杯备赛系列——倒计时50天!

蓝桥杯备赛系列 倒计时50天&#xff01; 前缀和和差分 知识点 **前缀和数组&#xff1a;**假设原数组用a[i]表示&#xff0c;前缀和数组用sum[i]表示&#xff0c;那么sum[i]表示的是原数组前i项之和&#xff0c;注意一般用前缀和数组时&#xff0c;原数组a[i]的有效下标是从…

【安卓基础3】Activity(一)

&#x1f3c6;作者简介&#xff1a;|康有为| &#xff0c;大四在读&#xff0c;目前在小米安卓实习&#xff0c;毕业入职 &#x1f3c6;本文收录于 安卓学习大全&#xff0c;欢迎关注 &#x1f3c6;安卓学习资料推荐&#xff1a; 视频&#xff1a;b站搜动脑学院 视频链接 &…

设置主从复制时发生报错Could not find first log file name in binary log index file‘;解决方案

如图所示&#xff0c;slave_io_runnind:no,slave_sql_running:yes 此时&#xff0c;主从配置错误&#xff0c;我们可以查看Last_IO_Error:来查看报错信息 此时&#xff0c;我们需要停止从服务器的主从服务&#xff0c; mysql> stop slave; Query OK, 0 rows affected, 1 w…

回显服务器的制作方法

文章目录 客户端和服务器TCP和UDP的特点UDP socket api的使用DatagramSocketDatagramPacketInetSocketAddress API 做一个简单的回显服务器UDP版本的回显服务器TCP版本的回显服务器 客户端和服务器 在网络中&#xff0c;主动发起通信的一方是客户端&#xff0c;被动接受的这一方…

1. 浏览器跨 Tab 窗口通信原理

浏览器跨 Tab 窗口通信原理 ![01 所谓多窗口下进行互相通信&#xff0c;是指在浏览器中&#xff0c;不同窗口&#xff08;包括不同标签页、不同浏览器窗口甚至不同浏览器实例&#xff09;之间进行数据传输和通信的能力。 当然&#xff0c;本文我们探讨的是纯前端的跨 Tab 页…

Web 前端 UI 框架Bootstrap简介与基本使用

Bootstrap 是一个流行的前端 UI 框架&#xff0c;用于快速开发响应式和移动设备优先的网页。它由 Twitter 的设计师和工程师开发&#xff0c;现在由一群志愿者维护。Bootstrap 提供了一套丰富的 HTML、CSS 和 JavaScript 组件&#xff0c;可以帮助开发者轻松地构建和定制网页和…

Springboot医院信息管理系统源码 带电子病历和LIS Saas应用+前后端分离+B/S架构

目录 系统特点 技术架构 系统功能 1、 标准数据维护 2、 收费&#xff08;门诊/住院&#xff09;系统 3、 药剂管理系统 4、 医生工作站系统 5、 护士工作站系统 6、电子病历系统 系统优点 云HIS系统简介 云HIS系统功能模块 门急诊挂号管理 门诊收费管理 门诊医…

Gitee教程2(完整流程)

1.配置git git config --global user.name "用户名" git config --global user.email "密码" 如何获取&#xff1f; gitee右上角加号点击新建仓库&#xff0c;仓库名随便起一个就行 找到这条命令&#xff0c;把这两句一个一个复制到vscode终端就行 2.创建g…

RabbitMQ的安装与使用

RabbitMQ的安装与使用 介绍一、RabbitMQ的安装1 查找镜像2 拉取镜像3 查看镜像4 创建容器5 查看容器6 访问测试 二、RabbitMQ的使用1 创建项目2 配置文件3 队列配置文件4 消费者5 生产者6 测试 三、交换器四、普通队列Demo五、死信队列Demo1 介绍2 示例2.1 配置2.2 生产者2.3 消…

【非常详细!】QT基础【二万字长文】

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;QT从基础到进阶 1 QMake2 Qt中三个窗口部件的区别2.1 QMainWindow2.2 QWidget2.3 QDialog 3 Visual Studio的QT项目与QtCreater项目相互转换3.1 QtCreater项目转VS项目3.2 VS项目转QtCreat…

百度地图海量点方案趟坑记录(百度地图GL版 + MapVGL + vue3 + ts)

核心需求描述 不同层级有不同的海量图标展示底层海量图标需要展示文字拖动、放大缩小都需要重新请求数据并展示固定地图中心点&#xff08;拖动、放大缩小&#xff0c;中心点始终在地图中心&#xff09; 示例图片&#xff1a;&#xff08;某些图片涉及公司数据&#xff0c;就未…

苍穹外卖Day02——总结2

前期文章 文章标题地址苍穹外卖Day01——总结1https://blog.csdn.net/qq_43751200/article/details/135466359?spm1001.2014.3001.5501苍穹外卖Day01——解决总结1中存在的问题https://lushimeng.blog.csdn.net/article/details/135473412 总结2 前期文章1. 新增员工模块1.1 …

初阶数据结构之---顺序表和链表(C语言)

引言-线性表 线性表&#xff1a; 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构&#xff0c;也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上…

Django学习笔记-创建第一个django项目

1.创建一个虚拟环境的python项目 2.点击解释器设置 3.安装django包 4.终端选择Command Prompt 5.创建django项目运行django-admin startproject demo01(自命名) 6.修改连接数据库为mysql 7.修改语言(中国汉语)和时区(亚洲上海)USE_TZ改为False,否则时区不生效 8.修改TEMPLA…

并发List、Set、ConcurrentHashMap底层原理

并发List、Set、ConcurrentHashMap底层原理 ArrayList: List特点&#xff1a;元素有放入顺序&#xff0c;元素可重复 存储结构&#xff1a;底层采用数组来实现 public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Clon…

C 语言基本语法及实用案例分享

一、什么是 C 语言&#xff1f; C语言是一种较早的程序设计语言&#xff0c;诞生于1972年的贝尔实验室。1972 年&#xff0c;Dennis Ritchie 设计了C语言&#xff0c;它继承了B语言的许多思想&#xff0c;并加入了数据类型的概念及其他特性。C语言是一门面向过程的计算机编程语…