【代码随想录】算法训练营 第二十天 第六章 二叉树 Part 6

654. 最大二叉树

题目

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

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

返回 nums 构建的 最大二叉树 

其实就是根据数组来构建二叉树,选定其中最大的数作为根节点,数组中左边的放在左子树,右边的放在右子树,然后接下来就是递归做下去,直到完成二叉树的构建。

思路

和昨天的根据两个遍历序列构建二叉树的思想差不多,只不过这题更简单,我们只要三步走,首先是构建中间节点,这就需要找到值最大的节点。

代码

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if (nums.size() == 1) {
            node->val = nums[0];
            return node;
        }
        int maxVal = 0;
        int index = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                index = i;
            }
        }
        node->val = maxVal;
        if (index > 0) {
            vector<int> newVec(nums.begin(), nums.begin() + index);
            node->left = constructMaximumBinaryTree(newVec);
        }
        if (index < nums.size() - 1) {
            vector<int> newVec(nums.begin() + index + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

617. 合并二叉树

题目

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

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

返回合并后的二叉树。

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

思路

对两个二叉树,合并相同位置的节点元素,这其实用前序遍历就可以完成,因为我们可以从上往下合并,从上往下的递归终止条件是其中一个遍历到空节点了,这时候就返回另一个二叉树此时遍历到的节点,因为两个二叉树的遍历是同步的;

接下来就是合并操作,这里我新定义了一个节点,然后将第一棵树的值传入,再加上第二棵树的值,最后就是继续合并子树了,递归调用函数本身即可。

代码

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL) return root2;
        if (root2 == NULL) return root1;
        TreeNode* root = new TreeNode(root1->val);
        root->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 。

思路

二叉搜索树的一个节点如果有左孩子和右孩子的话,则节点值大于左孩子的值,小于右孩子的值。

要注意root为空时的特判。

代码

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

98. 验证二叉搜索树

题目

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

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

相关文章

IntelliJ IDEA 2023.2.1 (Ultimate Edition) 版本 Git 如何合并多次的本地提交进行 Push

本心、输入输出、结果 文章目录 IntelliJ IDEA 2023.2.1 (Ultimate Edition) 版本 Git 如何合并多次的本地提交进行 Push前言为什么需要把多次本地提交合并合并提交的 2 种形式:事中合并、事后合并事中合并事后合并:支持拆分为多组提交弘扬爱国精神IntelliJ IDEA 2023.2.1 (U…

Android Camera App启动流程解析

前言&#xff1a;做了7年的camera app开发&#xff0c;给自己一个总结&#xff0c;算是对camera的一次告白吧。Camera被大家誉为手机的眼睛&#xff0c;是现在各大手机厂商的卖点&#xff0c;也是各大厂商重点发力的地方。Camera的重要性我就不在这里赘述了&#xff0c;让我们进…

【跟小嘉学习JavaWeb开发】第一章 开发环境搭建

系列文章目录 【跟小嘉学习JavaWeb开发】第一章 开发环境搭建 文章目录 系列文章目录[TOC](文章目录) 前言一、JDK的下载与安装1.1、关于JDK的版本问题 二、环境变量配置2.1、配置 JAVA_HOME、CLASSPATH2.2、配置path2.3、启动 cmd 三、编写代码、编译并执行3.1、编写代码&…

输出所有最长公共子序列

输出所有最长公共子序列 什么是最长公共子序列过程讲解完整程序代码&#xff08;python&#xff09; 什么是最长公共子序列 在力扣题库中的1143题有一道最长公共子序列&#xff0c;但是那个只是返回最长子序列的长度&#xff0c;而没有输出所有的最长子序列 通过上图中的举例…

Python制作采集直播弹幕小软件

嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 环境使用: Python 3.8 Pycharm模块使用: import requests >>> pip install requests import time import tkinter&#x1f447; &#x1f447; &#x1f447; 更多精彩机密、教程&#xff0c;尽在下方&#xff0c;…

AVL树详解

目录 AVL树的概念 旋转的介绍 单旋转 双旋转 旋转演示 具体实现 通过高度判断的实现 通过平衡因子判断的实现 AVL树的概念 AVL树是一种自平衡的平衡二叉查找树&#xff0c;它是一种高效的数据结构&#xff0c;可以在插入和删除节点时保持树的平衡&#xff0c;从而保证…

vivado时序分析-1

AMD Vivado ™ 集成设计环境 (IDE) 提供了多项报告命令 &#xff0c; 用于验证设计是否满足所有时序约束 &#xff0c; 以及是否准备好加载到应用开发板上。“Report Timing Summary ” &#xff08; 时序汇总报告 &#xff09; 属于时序验收报告 &#xff0c; 等同于 ISE De…

uniapp中picker 获取时间组件如何把年月日改成年月日默认时分秒为00:00:00

如图所示&#xff0c;uniapp中picker组件的日期格式为&#xff1a; 但后端要 2023-11-08 00:00:00格式 如何从2023-11-08转化为 2023-11-08 00:00:00&#xff1a;&#x1f447; const date new Date(e.detail.value);//"2023-11-17" date.setHours(0, 0, 0); // 2…

springboot actuator:开放全部(部分)端点、端点映射、端点保护

目录 开放全部端点&#xff08;不安全&#xff09;&#xff1a; 开放部分端点 端点映射 端口保护 1、 添加Spring Security依赖&#xff1a; 2、Spring Security简单配置类&#xff1a; 3、application.yml配置规则 4、写一个简单的controller 5、简单登录页面 目…

【hcie-cloud】【2】华为云Stack解决方案介绍、缩略语整理 【下】

文章目录 华为文档获取方式、云计算发展背景、坚实基座华为云Stack&#xff0c;政企只能升级首选智能数据湖仓一体&#xff0c;让业务洞见更准&#xff0c;价值兑现更快MRS&#xff1a;一个架构可构建三种数据湖&#xff0c;业务场景更丰富离线数据湖&#xff1a;提供云原生、湖…

强化您的应用安全,从app加固开始

强化您的应用安全&#xff0c;从app加固开始 目录 强化您的应用安全&#xff0c;从app加固开始 摘要 引言 1. 加密和数据保护 2. 代码混淆 3. 防止反编译 4. 安全测试 5. 更新和补丁 6. 权限控制 7. 输入验证和输出过滤 8. 日志记录和监控 9. 安全设计和架构 10.…

GoLong的学习之路(二十二)进阶,语法之并发(go最重要的特点)(channel的主要用法)

这一章是接上一章内容继续&#xff0c;上一章说到协程也就是goroutine&#xff0c;如何使用它&#xff0c;这一张是讲一种数据结构。当然这个章节的数据结构非常重要。可以说这个数据结构就是为了方便协程&#xff0c;才制作出来的。 单纯地将函数并发执行是没有意义的。函数与…

echart宽度100px原因(解决el-tabs里的echarts图表宽度不自适应,只有100px问题)

目录 问题描述产生原因处理方法1.使用echart 的API —— resize()2.使用 v-if 总结 问题描述 项目中在el-tabs下面使用了图表&#xff0c;发现图表的宽度始终只有100px 产生原因 首先echart初始化的组件宽度设置了width: 100%&#xff0c;那么本来这个时候&#xff0c;echar…

Flutter android和ios闪屏页配置

一.概念理解 闪屏页 1.当点击app开始的一瞬间&#xff0c;所呈现出来的页面就是闪屏页。 2.为什么会有闪屏也&#xff0c;由于app启动需要加载代码&#xff0c;这个过程需要耗时&#xff0c;在没有加载完成之前&#xff0c;是看不到app真正的页面。所以app在没有完全加载完时…

计算摄像技术03 - 数字感光器件

一些计算摄像技术知识内容的整理&#xff1a;感光器件的发展过程、数字感光器件结构、数字感光器件的指标。 目录 一、感光器件的发展过程 二、数字感光器件结构 &#xff08;1&#xff09;CCD结构 ① 微透镜 ② 滤光片 ③ 感光层 电荷传输模式 &#xff08;2&#xff09;CMOS结…

nigix安装以及遇到的问题

Nginx配置 nginx双击闪退如何解决 修改配置文件 端口冲突&#xff0c;将端口改为90 Nginx 动静分离&#xff08;前端的代码单独运行&#xff09; 将html文件夹里面的东西放到nginx里面的HTMl文件夹里面 负载均衡&#xff08;轮询&#xff0c;权重&#xff0c;哈希&#xff…

三数之和(双指针)

15. 三数之和 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三…

企业如何落地搭建商业智能BI系统

随着新一代信息化、数字化技术的应用&#xff0c;引发了新一轮的科技革命&#xff0c;现代化社会和数字化的联系越来越紧密&#xff0c;数据也变成继土地、劳动力、资本、技术之后的第五大生产要素&#xff0c;这一切都表明世界已经找准未来方向&#xff0c;前沿科技也与落地并…

数据库 高阶语句

目录 数据库 高阶语句 使用select 语句&#xff0c;用order by来对进行排序 区间判断查询和去重查询 如何对结果进行分组查询group by语句 limit 限制输出的结果记录&#xff0c;查看表中的指定行 通配符 设置别名&#xff1a;alias 简写就是 as 使用select 语句&#x…

CVE-2023-0179-Nftables整型溢出

前言 Netfilter是一个用于Linux操作系统的网络数据包过滤框架&#xff0c;它提供了一种灵活的方式来管理网络数据包的流动。Netfilter允许系统管理员和开发人员控制数据包在Linux内核中的处理方式&#xff0c;以实现网络安全、网络地址转换&#xff08;Network Address Transl…