Day20:LeedCode 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

 

示例 1：

 

3c71768d544b08a4c1fc10882b1581c3.jpeg

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

 

思路:采用先序遍历,先找到最大数构造root结点,再根据最大数将数组分为左区间和右区间,分别构造左子树和右子树

图解:

00414dc4916f49c3b17c2783d87865d6.png

递归三部曲:

1.确定返回值和参数类型 

传入需要构造树的数组,返回构造的树

2.确定终止条件

当我们传入的数组只有一个数时,说明该数一定构造叶节点,因为本题1 <= nums.length <= 1000

所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。但是我们分割数组后需要考虑数组长度为0的情况

  if(nums.length==1){
        root.val=nums[0];
        return root;
       }

3.确定单层递归逻辑

找到最大数构造根节点,分割数组为左右区间,构造左右子树

 //找到最大的数作为根节点
       int val=nums[0];
       int index=0;
       for(int i=0;i<nums.length;i++){
            if(val<nums[i]){
                val=nums[i];
                index=i;
            }
        }
        root.val=val;
       //构造左子树
    int[]  left_Tree=Arrays.copyOfRange(nums,0,index);
    int[] right_Tree=Arrays.copyOfRange(nums,index+1,nums.length);
    if(left_Tree.length>0)  root.left=constructMaximumBinaryTree(left_Tree);
    if(right_Tree.length>0)  root.right=constructMaximumBinaryTree(right_Tree);

完整代码参考:

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
       TreeNode root=  new TreeNode(0);;
       if(nums.length==1){
        root.val=nums[0];
        return root;
       }
       //找到最大的数作为根节点
       int val=nums[0];
       int index=0;
       for(int i=0;i<nums.length;i++){
            if(val<nums[i]){
                val=nums[i];
                index=i;
            }
        }
        root.val=val;
       //构造左子树
    int[]  left_Tree=Arrays.copyOfRange(nums,0,index);
    int[] right_Tree=Arrays.copyOfRange(nums,index+1,nums.length);
    if(left_Tree.length>0)  root.left=constructMaximumBinaryTree(left_Tree);
    if(right_Tree.length>0)  root.right=constructMaximumBinaryTree(right_Tree);
      return root;
    }
}

617. 合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

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

示例 1：

 

66856f28595d62336a7488e90f4366c5.jpeg

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

思路:本题的关键在于如何同时遍历两个二叉树,其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。

递归三要素:

1.确认返回值和参数类型

传入两个数的指针,返回合并后的树的指针

2.确定结束条件

当传入其中一颗树的指针为null时,返回另一个树的指针

3.单层递归逻辑

合并两棵树的当前结点,构造左右子树

root.val=root1.val+root2.val;
root.left=mergeTrees(root1.left,root2.left);
root.right=mergeTrees(root1.right,root2.right);

代码参考:

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

 

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

 

cf9e2268f197fce4c0126ecd32e1cd70.jpeg

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

二叉搜索树的特点是:

二叉搜索树是一个有序树：

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

递归三部曲:

1.确定递归函数的参数和返回值:

递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。

2.确定终止条件:

当我们遇到空结点说明找不到该数,返回Null

当当前结点的val等于我们要找的数,就返回该节点

 if(root==null) return null;
   if(root.val==val)return root;

3.每层递归逻辑:

如果当前结点数小于目标数,我们search右子树

如果当前结点数大于目标数,我们search左子树

代码参考:

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

 

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左

    子树

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

 

示例 1：

 

101099972afad76f4747a2a358a6c55d.jpeg

输入：root = [2,1,3]
输出：true

这道题目比较容易陷入两个陷阱：

陷阱1:

不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。

我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。

陷阱2

样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。

此时可以初始化比较元素为long的最小值。

思路:我们采用中序遍历,二叉搜索树先序遍历的数一定是递增的,用maxValue记录当前最大值,如果当前结点的值不大于maxValue,则返回false,只有当左右子树都为二叉搜索树并且maxValue<当前结点的val,这棵树才为二叉搜索树

图解:

18004084c7b04187b1ec4efede7fb1e7.png

代码参考:

class Solution {
    long  maxValue=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
    if(root==null)return true;
     boolean bl=isValidBST(root.left);
     if(maxValue<root.val){
       maxValue=root.val;
     }else return false;
     boolean br= isValidBST(root.right);
     return bl&&br;
    }
}

如果测试数据中有 long的最小值，怎么办？

不可能在初始化一个更小的值了吧。 建议避免 初始化最小值，如下方法取到最左面节点的数值来比较。

用一个结点保存最大值的结点,如果该结点为null,说明之前没有最大值,也就是我们现在遍历到了最左的结点了

 71d51afd804f46eea601d2edbfe17eb4.png

class Solution {
    TreeNode MaxNode=null;
    public boolean isValidBST(TreeNode root) {
    if(root==null)return true;
     boolean bl=isValidBST(root.left);
     if(MaxNode!=null&&MaxNode.val>=root.val){
     return false;
     }else MaxNode=root;
     boolean br= isValidBST(root.right);
     return bl&&br;
    }
}

 

 

 

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

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

相关文章

【Rust】——提取函数消除重复代码和泛型

【Rust】——提取函数消除重复代码和泛型

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…
阅读更多...
Java项目：75 springboot房产销售系统

Java项目：75 springboot房产销售系统

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 使用房产销售系统分为管理员和用户、销售经理三个角色的权限子模块。 管理员所能使用的功能主要有&#xff1a;首页、个人中心、用户管理、销售经理管…
阅读更多...
OpenCV4.9在iOS中安装

OpenCV4.9在iOS中安装

返回&#xff1a;OpenCV系列文章目录&#xff08;持续更新中......&#xff09; 上一篇&#xff1a;使用CUDA 为Tegra构建OpenCV-CSDN博客 下一篇&#xff1a; 警告&#xff01; 本教程可以包含过时的信息。 所需软件包 CMake 2.8.8 或更高版本Xcode 4.2 或更高版本 从 G…
阅读更多...
品牌出海必读：深入解析成功背后的5大底层逻辑

品牌出海必读：深入解析成功背后的5大底层逻辑

品牌出海是当今全球化时代中企业发展的重要策略之一。无论是传统制造业还是新兴科技公司&#xff0c;都在不同程度上关注着海外市场的拓展。然而&#xff0c;品牌出海并非仅仅是一个简单的营销策略&#xff0c;其背后蕴含着复杂的底层逻辑。本文Nox聚星将和大家探讨品牌出海的底…
阅读更多...
电脑桌面便签软件，好用的电脑桌面便签软件

电脑桌面便签软件，好用的电脑桌面便签软件

在数字化时代&#xff0c;我们的工作方式正在发生深刻的变革。作为现代办公一族&#xff0c;提升工作效率&#xff0c;管理好的灵感和待办事项变得尤为重要。而在众多的办公辅助工具中&#xff0c;电脑桌面便签软件以其便捷、实用的特点&#xff0c;深受广大办公族的喜爱。今天…
阅读更多...
C语言例4-17：从键盘输入一个年份year（4位十进制数），判断其是否是闰年

C语言例4-17：从键盘输入一个年份year（4位十进制数），判断其是否是闰年

算法分析&#xff1a; 如果X能被Y整除&#xff0c;则余数为0&#xff0c;即如果X%Y的值等于0&#xff0c;则表示X能被Y整除。首先将是否是闰年的标志leap初始值设置为0&#xff08;非闰年&#xff09;&#xff0c;仅当year为闰年时将leap的位置为1。 初始代码如下&#xff1a…
阅读更多...
踏入IOT安全世界：DIR-815路由器多次溢出漏洞分析复现

踏入IOT安全世界：DIR-815路由器多次溢出漏洞分析复现

前言 在进行IOT安全领域的学习和实践中&#xff0c;经典漏洞的复现是必不可少的一环。本文将介绍一个经典漏洞&#xff0c;涉及到Binwalk、firmware-mod-kit、FirmAE等工具的使用&#xff0c;以及对DIR-815路由器中多次溢出漏洞的复现过程。 固件下载地址&#xff1a;https:/…
阅读更多...
安捷伦Agilent 34401A数字万用表

安捷伦Agilent 34401A数字万用表

181/2461/8938产品概述&#xff1a; Agilent34401A 万用表将准确性、速度、测量简便性和多功能性结合到坚固的 6 1/2 位数字万用表中&#xff0c;无论在工作台上还是在系统中都同样适用。您可以以 5 1/2 位数的价格获得 6 1/2 位数的性能。除了直流和交流电压、直流和交流电流…
阅读更多...
golang+vue微服务电商系统

golang+vue微服务电商系统

golangvue微服务电商系统 文章目录 golangvue微服务电商系统一、项目前置准备二、项目简介三、代码GItee地址 golang、vue redis、mysql、gin、nacos、es、kibana、jwt 一、项目前置准备 环境的搭建 官方go开发工程师参考地址&#xff1a;https://blog.csdn.net/qq23001186/cat…
阅读更多...
【数据结构与算法】直接插入排序和希尔排序

【数据结构与算法】直接插入排序和希尔排序

引言 进入了初阶数据结构的一个新的主题——排序。所谓排序&#xff0c;就是一串记录&#xff0c;按照其中的某几个或某些关键字的大小&#xff08;一定的规则&#xff09;&#xff0c;递增或递减排列起来的操作。 排序的稳定性&#xff1a;在一定的规则下&#xff0c;两个值…
阅读更多...
Web3 游戏周报（3.17-3.23）

Web3 游戏周报（3.17-3.23）

【3.17-3.23】Web3 游戏行业动态&#xff1a; Saga 宣布成立 Web3 游戏发行部门 Saga Origins Web3 游戏平台 Portal 宣布将于周四开放质押功能 STP 推出基于 Base 的 AI 增强游戏 Layer3 Clique Merlin 生态游戏项目 BitRealms 完成 Pre-Seed 轮融资 Telos 在游戏侧链发布…
阅读更多...
Open CASCADE学习|显示文本

Open CASCADE学习|显示文本

目录 1、修改代码 Viewer.h&#xff1a; Viewer.cpp&#xff1a; 2、显示文本 OpenCasCade 你好啊 霜吹花落 1、修改代码 在文章《Open CASCADE学习|显示模型》基础上&#xff0c;增加部分代码&#xff0c;实现对文本显示的支持&#xff0c;具体如下&#xff1a; Viewer…
阅读更多...
入门编程，一定要从C语言开始吗？

入门编程，一定要从C语言开始吗？

对于编程入门学习者&#xff0c;C语言肯定不是首选。建议先确定自己的发展方向&#xff0c; 如果打算做Web 开发&#xff0c;可以先从学习HTML,CSS,Javascript开始&#xff0c;后台使用Node.JS&#xff0c;也是用Javascript 来编程, 可降低入门门槛。 在开始前我有一些资料…
阅读更多...
MySQL索引优化、SQL优化-持续更新

MySQL索引优化、SQL优化-持续更新

背景 成本最低的优化手段&#xff0c;面试常问的面试题。 下面主要是讲InnoDB存储引擎的索引&#xff0c;InnoDB也是实际项目用的最多的存储引擎。 优势 提高数据查询效率。 缺点 占用空间、降低了增、删、改速度&#xff0c;因为要维护索引 原理 底层是B树数据结构。 …
阅读更多...
关于Web APP 促进临床预测模型进入临床实践的讨论

关于Web APP 促进临床预测模型进入临床实践的讨论

关于Web APP 促进临床预测模型进入临床实践的讨论 关键词&#xff1a; 临床预测模型、Web APP、实践、标准、讨论、分享 近年来&#xff0c;随着机器学习技术的快速发展&#xff0c;临床预测模型在辅助诊断、预后评估、治疗方案选择等方面展现出巨大潜力。然而&#xff0c;将…
阅读更多...
工时表软件：项目管理的效率利器

工时表软件：项目管理的效率利器

在当今的项目管理实践中&#xff0c;时间是最宝贵的资产之一。精准地追踪和管理项目工时对于项目的成功至关重要。工时表软件作为一种现代管理工具&#xff0c;其应用不仅简化了项目管理流程&#xff0c;还提高了工作效率&#xff0c;已成为现代企业管理不可或缺的一项利器。 …
阅读更多...
[Vue warn]: Invalid vnode type when creating vnode: false

[Vue warn]: Invalid vnode type when creating vnode: false

如题&#xff0c;意思是创建vnode时&#xff0c;vnode类型无效:false。 根据右边的索引点进去&#xff0c;发现定位的是组件loading。搜索loading发现声明了变量loading&#xff0c;更改后问题消失。
阅读更多...
MySQL数据库高阶语句①

MySQL数据库高阶语句①

目录 一.按关键字排序 1.单字段排序 &#xff08;1&#xff09;按分数排序 &#xff08;2&#xff09;结合where进行条件筛选 2.多字段排序 &#xff08;1&#xff09;查询学生信息先按兴趣id升序排序&#xff0c;再按id升序排序 &#xff08;2&#xff09;查询信息按兴…
阅读更多...
视频素材网站哪个比较好？8个优质视频素材软件app推荐

视频素材网站哪个比较好？8个优质视频素材软件app推荐

在探索那些能够让视频作品焕发生机的宝藏网站时&#xff0c;一个好的短视频素材库不仅能提升作品的视觉效果&#xff0c;还能赋予作品更深的情感层次。为了帮助你更好地寻找到这些珍贵的资源&#xff0c;以下是一系列精选的视频素材网站&#xff0c;全面支持你的视频创作需求。…
阅读更多...
低照度图像增强算法---传统算法篇

低照度图像增强算法---传统算法篇

YOLOv8n原图检测YOLOv8n增强后检测召回率和置信度都有提升 前言 这篇博客讲讲低照度，大家都催我出一些内容，没想到这么多同学搞这个，恰好我也做过这方面的一些工作，那今天就来讲解一些方法，低照度的图像增强大体分“传统算法”和“深度学习算法”； 目前低照度的图像增…
阅读更多...
最新文章

Copyright @ 2022~2023