代码随想录第十七天

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.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* leveltravel(int* num,int start,int numsSize)
{if(start >= numsSize){return NULL;}int max = num[start];int index = start;for(int i = start+1;i < numsSize;i++){if(num[i] > max){max = num[i];index = i;}else{max = max;}}struct TreeNode* node = malloc(sizeof(struct TreeNode));node->val = max;node->left = leveltravel(num,start,index);node->right = leveltravel(num,index+1,numsSize);return node;
}
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {return leveltravel(nums,0,numsSize);
}

617.合并二叉树

给你两棵二叉树: root1root2

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

思路:

很简单的递归使用,但是要注意在递归时要用三元表达式来对元素进行判断,看它是否为空指针,其他的就是简单的判断,很快就能做出来。

解答:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* levelmerge(struct TreeNode* root1,struct TreeNode* root2)
{if(root1 == NULL && root2 == NULL){return NULL;}struct TreeNode* node = malloc(sizeof(struct TreeNode));if(root1 != NULL && root2 != NULL)node->val = root1->val + root2->val;else if(root1 != NULL && root2 == NULL)node->val = root1->val;else if(root1 == NULL && root2 != NULL)node->val = root2->val;node->left = levelmerge(root1?root1->left:NULL,root2?root2->left:NULL);node->right = levelmerge(root1?root1->right:NULL,root2?root2->right:NULL);return node;
}
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {return levelmerge(root1,root2);
}

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

思路:

当根节点的值与目标值相等时,我们会返回根节点,当根节点为空指针时,我们也会返回根节点。所以这是一个基线条件,同时这是一个二叉搜索树,左子节点小于根节点,根节点小于子右节点,所以当根节点大了时我们就选左节点,当根节点小了的话我们就选右节点。最终得到答案。

解答:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* searchBST(struct TreeNode* root, int val) {if(root == NULL || root->val == val)return root;struct TreeNode* node = NULL;if(root->val > val)node = searchBST(root->left,val);if(root->val < val)node = searchBST(root->right,val);return node;
}

98.验证二叉搜索树

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

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

  • 节点的左

    子树

    只包含

    小于

    当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

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

示例 2:

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

提示:

  • 树中节点数目范围在[1, 104]
  • -2^31 <= Node.val <= 2^31 - 1

思路:

这里要注意对于每个节点,左子树中的所有节点值都小于该节点的值。右子树中的所有节点值都大于该节点的值。所以我们这里设置一个范围,在这个范围里,就是正确的,不在这个范围内就不对了,然后返回最终答案就行了。

解答:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool travellevel(struct TreeNode* root,long min,long max)
{if(root == NULL){return true;}if(root->val <= min || root->val >= max){return false;}return travellevel(root->left,min,root->val) && travellevel(root->right,root->val,max);
}
bool isValidBST(struct TreeNode* root) {return travellevel(root,LONG_MIN,LONG_MAX);
}

反思

今天的题并不难,最主要的还是每天坚持练习,到后面对于这些题都有了自己的思想,也就都能做了。

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

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

相关文章

虚拟化环境中的精简版 Android 操作系统 Microdroid

随着移动设备的普及和应用场景的多样化&#xff0c;安全性和隐私保护成为了移动操作系统的重要课题。Google推出的Microdroid&#xff0c;是一个专为虚拟化环境设计的精简版Android操作系统&#xff0c;旨在提供一个安全、隔离的执行环境。本文将详细介绍Microdroid的架构、功能…

【Docker系列】指定系统平台拉取 openjdk:8 镜像

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

(七)Python运算符和优先级

一、算数运算符 算数运算符&#xff0c;如下表所示&#xff1a; x1 y2 z3 # 加法运算 axy print(a,a) # 减法运算 by-x print(b,b) # 乘法运算 cy*z print(c,c) # 除法运算 dz/y print(d,d) # 取模运算 ez%y print(e,e) # 幂运算 fy**z print(f,f) 输出结果&#xff1a; 二…

Linux中使用NGINX

NGINX简介 Nginx&#xff08;engine x&#xff09;是俄罗斯人编写的十分轻量级的HTTP服务器是一个高性能的HTTP和反向代理服务器&#xff0c;同时也是一个IMAP/POP3/SMTP代理服务器官方网站&#xff1a;http://nginx.org/ NGINX概述 Nginx默认配置文件&#xff1a;/etc/ngin…

数据结构之线段树

线段树 线段树&#xff08;Segment Tree&#xff09;是一种高效的数据结构&#xff0c;广泛应用于计算机科学和算法中&#xff0c;特别是在处理区间查询和更新问题时表现出色。以下是对线段树的详细解释&#xff1a; 一、基本概念 线段树是一种二叉搜索树&#xff0c;是算法竞…

【C++】继承的理解

1.继承的概念和定义 1.1继承的概念 继承 (inheritance) 机制是面向对象程序设计 使代码可以复用 的最重要的手段&#xff0c;它允许程序员在 保 持原有类特性的基础上进行扩展 &#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称派生类。继承 呈现了面向对象 程序…

C++ 详细讲解 洛谷P1428 小鱼比可爱

&#xff08;其实这道题难度不高&#xff0c;但是博主正在适应c语言加上这道题目太可爱了所以忍不住发发~&#xff09; 目录 1.题目要求 2.题目解读 3.代码实现 1.题目要求 2.题目解读 这道题需要使用c中的容器储存小鱼的可爱程度和不如自己可爱的小鱼的数目&#xff0c;…

Android亮屏Job的功耗优化方案

摘要: Job运行时会带来持锁的现象,目前灭屏放电Job的锁托管已经有doze和绿盟标准监管,但是亮屏时仍旧存在过长的持锁现象,故为了优化功耗和不影响用户体验下,新增亮屏放电下如果满足冻结和已运行过一次Job,则进行job限制,当非冻结时恢复的策略 1.现象: (gms_schedu…

Spring1(初始Spring 解耦实现 SpringIOC SpringDI Spring常见面试题)

Spring1 创建项目集成maven创建一个Maven项目实现&#xff1a; 初识SpringSpring简介Spring的发展历史Spring之父体系结构生态系统官方文档解耦实现JDBCSpringBoot整合MyBatis和lombok&#xff0c;开启驼峰映射三层思想 SpringIOC实现 SpringDIset注入全部代码&#xff1a;实现…

服务器新建用户

文章目录 前言一、步骤二、问题三、赋予管理员权限总结 前言 环境&#xff1a; 一、步骤 创建用户需要管理员权限sudo sudo useradd tang为用户设置密码 sudo passwd tang设置密码后&#xff0c;可以尝试使用 su 切换到 tang 用户&#xff0c;确保该用户可以正常使用&#…

leetcode-88-合并两个有序数组

题解&#xff1a; 解法一&#xff1a;从后向前同时遍历两个数组&#xff0c;因为nums1后面是0&#xff0c;从后遍历节省空间。 1、定义三个指针&#xff0c;分别为&#xff1a;len1m-1指向nums1的最后一个非0数字&#xff1b;len2n-1指向nums2的最后一个数字&#xff1b;len3…

操作系统(10) (并发(2)------基于软件/硬件/操作系统层面解决两个进程之间的临界区问题/抢占式/非抢占式内核)

目录 1. 基于软件层面(Petersons Solution) Petersons Solution 满足三个要求: 好处: 缺点 2. 基于硬件层面 1. Disabling Interrupts (禁用中断) 概念解释&#xff1a; 代码框架&#xff1a; 要求&#xff1a; 禁用中断的好处与问题&#xff1a; 2. Test and Set Lock (…

Java | Leetcode Java题解之第526题优美的排列

题目&#xff1a; 题解&#xff1a; class Solution {public int countArrangement(int n) {int[] f new int[1 << n];f[0] 1;for (int mask 1; mask < (1 << n); mask) {int num Integer.bitCount(mask);for (int i 0; i < n; i) {if ((mask & (1…

2024年大厂AI大模型面试题精选与答案解析

前言 随着AI市场&#xff0c;人工智能的爆火&#xff0c;在接下来的金九银十招聘高峰期&#xff0c;各大科技巨头和国有企业将会对AGI人才的争夺展开一场大战&#xff0c;为求职市场注入了新的活力。 为了助力求职者在面试中展现最佳状态&#xff0c;深入理解行业巨头的选拔标…

智能网联汽车:人工智能与汽车行业的深度融合

内容概要 在这个快速发展的时代&#xff0c;智能网联汽车已经不再是科幻电影的专利&#xff0c;它正在悄然走进我们的日常生活。如今&#xff0c;人工智能&#xff08;AI&#xff09;技术与汽车行业的结合犹如一场科技盛宴&#xff0c;让我们看到了未来出行的新方向。通过自动…

AI大模型重塑软件开发:从代码自动生成到智能测试

随着AI技术的不断发展&#xff0c;AI大模型在软件开发领域的应用日益广泛。从代码自动生成到智能测试&#xff0c;AI大模型正在深刻改变着软件开发的各个环节&#xff0c;重塑着整个开发流程。本文将探讨AI大模型的定义、应用场景、优势以及挑战&#xff0c;并展望未来的发展趋…

【基础】os模块

前言 1、os是operation system&#xff08;操作系统&#xff09;的缩写&#xff1b;os模块就是python对操作系统操作接口的封装。os模块提供了多数操作系统的功能接口函数。&#xff08;OS模块提供了与操作系统进行交互的函数&#xff09; 2、操作系统属于Python的标准实用程…

算法学习027 c++蛇形三角形填充 二维数组常规应用 中小学算法思维学习 比赛算法题解 信奥算法解析

目录 C蛇形三角形填充 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、运行结果 五、考点分析 六、推荐资料 C蛇形三角形填充 一、题目要求 1、编程实现 输入一个正整数N&#xff0c;输出N行的蛇形数字三角形&#xff08;见输出样例&#xf…

[vulnhub]DC: 1

https://www.vulnhub.com/entry/dc-1,292/ 主机发现端口扫描 使用nmap扫描网段类存活主机 因为靶机是我最后添加的&#xff0c;所以靶机IP是156 nmap -sP 192.168.75.0/24 // Starting Nmap 7.93 ( https://nmap.org ) at 2024-09-28 12:48 CST Nmap scan rep…

PyQt5的安装与简介

目录 一、介绍 二、PyQt5的安装 1、安装PyQt5 2、安装Qt的工具包 三、配置Qt工具 1、配置Designer &#xff08;1)、打开pycharm&#xff0c;找到设置选项 &#xff08;2&#xff09;、找到工具-->外部工具 &#xff08;3&#xff09;、点击号&#xff0c;创建外部工…