代码随想录第19天

654. 最大二叉树

已解答

中等

相关标签

相关企业

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

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

返回 nums 构建的 最大二叉树 

示例 1:

输入: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 的节点。
        - 空数组,无子节点。

示例 2:

输入:nums = [3,2,1]
输出:[3,null,2,null,1]

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • nums 中的所有整数 互不相同

/**
 * 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 constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {
            return null;
        }
        if (rightIndex - leftIndex == 1) {
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;
        int maxVal = nums[maxIndex];
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums,0,nums.length);
    }
}

代码

测试用例

测试用例

测试结果

617. 合并二叉树

已解答

简单

相关标签

相关企业

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

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

返回合并后的二叉树。

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

示例 1:

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

示例 2:

输入:root1 = [1], root2 = [1,2]
输出:[2,2]

提示:

  • 两棵树中的节点数目在范围 [0, 2000] 内
  • -104 <= Node.val <= 104

请问您在哪类招聘中遇到此题?

1/5

社招

校招

实习

未遇到

通过次数

483K

提交次数

609K

通过率

79.3%

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null){
            return root2;
        }
        if(root2 == null){
            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 。

示例 1:

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

示例 2:

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

提示:

  • 树中节点数在 [1, 5000] 范围内
  • 1 <= Node.val <= 107
  • root 是二叉搜索树
  • 1 <= val <= 107

 

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

代码

测试用例

测试用例

测试结果

98. 验证二叉搜索树

已解答

中等

相关标签

相关企业

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

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

  • 节点的左

    子树

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

示例 1:

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

示例 2:

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

提示:

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1
class Solution {

    TreeNode max;

    public boolean isValidBST(TreeNode root) {
         if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST(root.left);
        if (!left) {
            return false;
        }
        // 中
        if (max != null && root.val <= max.val) {
            return false;
        }
        max = root;
        // 右
        boolean right = isValidBST(root.right);
        return right;
    }
}

 有序数组不能出现前一个数值大于后面的情况

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

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

相关文章

影院座位选择简易实现(uniapp)

界面展示 主要使用到uniap中的movable-area&#xff0c;和movable-view组件实现。 代码逻辑分析 1、使用movable-area和movea-view组件&#xff0c;用于座位展示 <div class"ui-seat__box"><movable-area class"ui-movableArea"><movab…

【QT学习】5.控件

一。控件的了解 1.控件作用 拖拽页面&#xff0c;所见即所得。 2.创建控件 3.向qt项目中添加资源 3.1显示图片 项目右键--》add new 创建结果&#xff1a; 添加资源到文件中 补充&#xff1a;使用代码的方式添加图片 3.2显示动图 1.添加动图资源 添加资源 2.显示动图 3.3显示…

基于单片机电子硬币储存器的设计

**单片机设计介绍&#xff0c;基于单片机电子硬币储存器的设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机电子硬币储存器的设计概要主要涵盖了硬件设计、软件设计、硬币识别、计数与储存等核心功能。以下是对该设…

OWASP TOP10 漏洞详解

前言 该内容是 OWASP TOP 10 的学习笔记&#xff0c;笔记内容来源 B 站龙哥的视频【12.Top漏洞10&#xff1a;服务器请求伪造_哔哩哔哩_bilibili】 一、访问控制崩溃 概念 未对通过身份验证的用户实施恰当的访问控制。攻击者可以利用这些缺陷访问未经授权的功能或数据&#xf…

【Linux】环境基础开发工具使用——gcc/g++使用

Linux编译器-gcc/g使用 1. 背景知识 1. 预处理&#xff08;进行宏替换 ) 2. 编译&#xff08;生成汇编 ) 3. 汇编&#xff08;生成机器可识别代码&#xff09; 4. 连接&#xff08;生成可执行文件或库文件 ) 2. gcc如何完成 格式 gcc [ 选项 ] 要编译的文件 [ 选…

阿德勒、荣格、埃里克森、霍妮、弗洛姆、沙利文的新精神分析理论

新精神分析理论&#xff0c;强调自我的自主性及其整合与调节功能&#xff0c;强调文化和社会因素对人格的重大影响。 一、阿德勒的个体心理学 阿德勒&#xff0c;是一个男人努力克服自卑感的优秀样板。阿德勒写了《超越与自卑》。 阿德勒&#xff0c;向意识层面扩展精神分析…

c++11的重要特性3

目录 1、lambda表达式 C98中的一个例子 lambda表达式的 lambda表达式语法 函数对象与lambda表达式 3、可变参数模板 递归获取 逗号表达式展开参数包 2、包装器 function包装器 bind 1、lambda表达式 C98中的一个例子 在C98中&#xff0c;如果想要对一个数据集合中的元素进…

NetSuite 自定义记录类型的权限控制

在近期的一个定制项目中&#xff0c;遭受了一次用户洗礼。有个好奇宝宝把我们的一个自定义类型的表记录进行了删除&#xff0c;导致一个重要功能失败。算是给我们扎实上了一课。自定义类型的权限也需要重视起来。所以&#xff0c;今朝我们记录下这个设置&#xff0c;同时写给未…

C++ setw() 函数

C setw() 函数 分类 编程技术 C setw() 函数用于设置字段的宽度&#xff0c;语法格式如下&#xff1a; setw(n) n 表示宽度&#xff0c;用数字表示。 setw() 函数只对紧接着的输出产生作用。 当后面紧跟着的输出字段长度小于 n 的时候&#xff0c;在该字段前面用空格补齐&…

《QT实用小工具·十五》多种样式的开关控件

1、概述 源码放在文章末尾 目前实现了三种样式的开关控件按钮&#xff0c;如下所示&#xff1a; 项目部分代码如下所示&#xff1a; #ifndef IMAGESWITCH_H #define IMAGESWITCH_H/*** 图片开关控件 * 1. 自带三种开关按钮样式。* 2. 可自定义开关图片。*/#include <QWid…

SpringBoot新增员工模块开发

需求分析与设计 一&#xff1a;产品原型 一般在做需求分析时&#xff0c;往往都是对照着产品原型进行分析&#xff0c;因为产品原型比较直观&#xff0c;便于我们理解业务。 后台系统中可以管理员工信息&#xff0c;通过新增员工来添加后台系统用户。 新增员工原型&#xf…

Vue中如何使用Tailwind CSS样式?多次引用不成功?具体步骤怎么做?

一、安装Tailwind CSS和依赖 在你的Vue项目中安装Tailwind CSS及其依赖。你可以使用npm或yarn来安装。 npm install tailwindcsslatest postcsslatest autoprefixerlatest # 或者yarn add tailwindcsslatest postcsslatest autoprefixerlatest 二、初始化Tailwind CSS np…

Linux常用命令-网络管理

文章目录 ping基本用法主要选项常见用途和理解输出注意事项 ifconfig基本用法配置网络接口示例高级功能 netstat基本用法常用选项示例注意事项 wget主要特点基本用法常见选项 示例注意事项 curl主要特点基本用法常见选项 示例注意事项 参考资料在线文档和手册图书在线教程和指南…

YOLO-World:实时开放词汇对象检测(论文+代码)

目录 一、YOLO-World摘要以及主要贡献 1.1摘要 1.2主要贡献 二、YOLO-World模型创新点总结 2.1YOLO Detector 2.2Text Encoder 2.3Re-parameterizable Vision-Language PAN 2.4核心创新点总结 三、如何应用 3.1推理预测 3.2自定义词汇推理 3.3自定义词汇类别…

Struts2的入门:新建项目——》导入jar包——》jsp,action,struts.xml,web.xml——》在项目运行

文章目录 配置环境tomcat 新建项目导入jar包新建jsp界面新建action类新建struts.xml,用来配置action文件配置Struts2的核心过滤器&#xff1a;web.xml 启动测试给一个返回界面在struts.xml中配置以实现页面的跳转&#xff1a;result再写个success.jsp最后在项目运行 配置环境 …

C++从入门到精通——类的定义及类的访问限定符和封装

类的定义及类的访问限定符和封装 前言一、类的定义类的两种定义方式成员变量命名规则的建议示例 二、类的访问限定符和封装访问限定符访问限定符说明C为什么要出现访问限定符例题 封装例题 前言 类的定义是面向对象编程中的基本概念&#xff0c;它描述了一类具有相同属性和方法…

Atlas 200 DK开发者套件的网络连接

一、参考资料 Atlas 200 DK官方文档 二、常用操作 1. Micro SD制卡 在windows系统上&#xff0c;一键制卡的步骤与Atlas 200I DK类似&#xff0c;但步骤更简单&#xff0c;详细步骤请参考&#xff1a;Windows系统制卡 2. Atlas 200 DK与PC机通信 2.1 准备工作 准备一根安…

一些好玩的东西

这里写目录标题 递归1.递归打印数组和链表?代码实现原理讲解二叉树的 前 中 后 序位置 参考文章 递归 1.递归打印数组和链表? 平常我们打印数组和链表都是 迭代 就好了今天学到一个新思路–>不仅可以轻松正着打印数组和链表 , 还能轻松倒着打印(用的是二叉树的前中后序遍…

vue事件代理

数据代理 Object.defineProperty 常见属性值 get和set函数 理解数据代理 Vue中的数据代理 Vue中的数据代理小结 事件处理 v-bind 事件处理小结 数据代理 Object.defineProperty 常见属性值 <body> <script type"text/javascript"> let person{n…

C++:逻辑运算符-非与或(19)

!非!a如果a为假&#xff0c;那么当前他就是真&#xff0c;如果a是真&#xff0c;那么他直接就是假&&与a&&ba与b都为真&#xff0c;那么就是真&#xff0c;如果两个里面有一个为假那么就是假||或a||ba或b有一个为真&#xff0c;那么就是真 非&#xff08;!&…