【牛客面试必刷TOP101】Day7.BM31 对称的二叉树和BM32 合并二叉树
作者简介:大家好,我是未央;
博客首页:未央.303
系列专栏:牛客面试必刷TOP101
每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!!!!!
文章目录
前言
一、对称的二叉树
题目描述
解题分析
二、合并二叉树
题目描述
解题分析
总结

前言
一、对称的二叉树
题目描述
描述:
给定一棵二叉树,判断其是否是自身的镜像(即:是否对称)
例如:
下面这棵二叉树是对称的:
下面这棵二叉树不对称:
数据范围:节点数满足 0≤n≤1000,节点上的值满足∣val∣≤1000;
要求:空间复杂度 O(n),时间复杂度O(n)
备注:
你可以用递归和迭代两种方法解决这个问题;
示例1:
示例2:

解题分析
题目的主要信息:
- 判断一棵二叉树是否是镜像,即判断二叉树是否是轴对称图形
轴对称:
非轴对称:
本题我们采用递归的方法进行解答更加简单;
解题思路:
前序遍历的时候我们采用的是“根左右”的遍历次序,如果这棵二叉树是对称的,即相应的左右节点交换位置完全没有问题,那我们是不是可以尝试“根右左”遍历,按照轴对称图像的性质,这两种次序的遍历结果应该是一样的。
不同的方式遍历两次,将结果拿出来比较看起来是一种可行的方法,但也仅仅可行,太过于麻烦。我们不如在遍历的过程就结果比较了。而遍历方式依据前序遍历可以使用递归:
- 本级任务: 每个子问题,需要按照上述思路,“根左右”走左边的时候“根右左”走右边,“根左右”走右边的时候“根右左”走左边,一起进入子问题,需要两边都是匹配才能对称。
- 终止条件: 当进入子问题的两个节点都为空,说明都到了叶子节点,且是同步的,因此结束本次子问题,返回true;有当进入子问题的两个节点只一个为空,或是元素值不相等,说明这里的对称不匹配,同样结束本次子问题,返回false。
- 返回值: 每一级将子问题是否匹配的结果往上传递。
解题步骤:
- step 1:两种方向的前序遍历,同步过程中的当前两个节点,同为空,属于对称的范畴。
- step 2:当前两个节点只有一个为空或者节点值不相等,已经不是对称的二叉树了。
- step 3:第一个节点的左子树与第二个节点的右子树同步递归对比,第一个节点的右子树与第二个节点的左子树同步递归比较。
图示过程分析:
代码编写:

二、合并二叉树
题目描述
描述:
已知两颗二叉树,将它们合并成一颗二叉树。
合并规则是:都存在的结点,就将结点值加起来,否则空的位置就由另一个树的结点来代替。
例如:
两颗二叉树是:
合并后的树为:
数据范围:树上节点数量满足 0≤n≤500,树上节点的值一定在32位整型范围内。
进阶:空间复杂度O(1) ,时间复杂度O(n);
示例1:
示例2:

解题分析
题目的主要信息:
- 合并(相加)二叉树位置相同的节点;
- 缺少的节点用另一棵树来补,若都缺则返回NULL;
解题思路:
递归前序遍历
要将一棵二叉树的节点与另一棵二叉树相加合并,肯定需要遍历两棵二叉树,那我们可以考虑同步遍历两棵二叉树,这样就可以将每次遍历到的值相加在一起。遍历的方式有多种,这里推荐前序递归遍历。
解题步骤:
- step 1:首先判断t1与t2是否为空,若一个为空则用另一个代替,若都为空,返回的值也是空。
- step 2:然后依据前序遍历的特点,优先访问根节点,将两个根点的值相加创建到新树中。
- step 3:两棵树再依次同步进入左子树和右子树。
代码编写:
总结

相关文章:
【牛客面试必刷TOP101】Day7.BM31 对称的二叉树和BM32 合并二叉树
作者简介:大家好,我是未央; 博客首页:未央.303 系列专栏:牛客面试必刷TOP101 每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!!!&…...
U盘怎么设置为只读?U盘怎么只读加密?
当将U盘设置为只读模式时,将只能查看其中数据,无法对其中数据进行编辑、复制、删除等操作。那么,怎么将U盘设置成只读呢? U盘如何设置成只读? 有些U盘带有写保护开关,当打开时,U盘就会处于只读…...
为什么MyBatis是Java数据库持久层的明智选择
在Java应用程序的开发中,选择合适的数据库持久层框架至关重要。一个明智的选择可以帮助开发人员更好地管理数据库交互、提高性能和简化开发工作。 (一)为什么要选MyBatis JDBCHibernate / JPAMyBatis简单直接ORM轻量动态SQL关联查询开发效率…...
二叉搜索树--查询节点-力扣 700 题
例题细节讲过(二叉搜索树的基础操作-CSDN博客),下面给出递归实现 public TreeNode searchBST(TreeNode node, int val) {if(node null) {return null;}if(val < node.val) {return searchBST(node.left, val);} else if(node.val < val) {return searchBST(…...
YOLOv3 | 核心主干网络,特征图解码,多类损失函数详解
https://zhuanlan.zhihu.com/p/76802514) 文章目录 1. 核心改进1.1主干网络1.2 特征图解码1.2.1 检测框(位置,宽高)解码1.2.2 检测置信度解码1.2.3 类别解码 1.3 训练损失函数1.3.1 正负样本定义1.3.2 损失函数 1. 核心改进 1.1主干网络 更…...
Java架构师API设计
目录 1 导学2 架构师的角度来审视API2.1 API狭隘理解2.2 API广义理解2.3 API的用途不同定义2.4 面向抽象编程的Java开发2.5 API在提高系统的可维护性和可扩展性方面的作用3 架构师必备的API设计原则3.1 标准化原则3.2 易用性原则3.3 扩展性原则3.4 兼容性原则3.5 抽象性原则3.6…...
.net也能写内存挂
最近在研究.net的内存挂。 写了很久的c,发现c#写出来的东西实在太香。 折腾c#外挂已经有很长时间了。都是用socket和c配合。 这个模式其实蛮成功的,用rpc调用的方式加上c#的天生await 非常好写逻辑 类似这样 最近想换个口味。注入托管dll到非托管进程 这样做只…...
python学习笔记2-数字转化为String
题目链接 str() 强制转换, sorted() 转换为有序列表,join() 将列表中的元素连接到字符串中,然后奇偶位组合成数字 class Solution:def splitNum(self, num: int) -> int:stnum "".join(sorted(str(num)))num1, num2 int(stn…...
MAC版Gradle构建Spring5.X源码阅读环境
前言: 三年前鄙人有幸在现已几乎报废的Window的DELL中搭建过Spring源码环境,今天,Mac版的搭建,来了。 本篇文章环境搭建:Spring5.2.1 Gradle5.6.3-all jdk8 IDEA2022.3版本 文章目录 1、Spring源码下载2、Gradle下载…...
Linux 常用通配符
通配符是一种特殊语句,主要有星号(*)和问号(?),用来模糊搜索文件。当查找文件夹时,可以使用它来代替一个或多个真正字符;当不知道真正字符或者懒得输入完整名字时&#x…...
Python皮卡丘
系列文章 序号文章目录直达链接1浪漫520表白代码https://want595.blog.csdn.net/article/details/1306668812满屏表白代码https://want595.blog.csdn.net/article/details/1297945183跳动的爱心https://want595.blog.csdn.net/article/details/1295031234漂浮爱心https://want…...
【数据结构与算法】三种简单排序算法,包括冒泡排序、选择排序、插入排序算法
冒泡排序算法 冒泡排序他是通过双重循环对每一个值进行比较,将小的值向后移动,以达到最终排序的结果,他的时间复杂度为O(n^2)。 /*** 冒泡排序* param arr*/public static void bubbleSort(int[] arr){int l arr.length;for (int i 0; i <…...
视频太大怎么压缩变小?超过1G的视频这样压缩
视频已经成为了我们日常生活中不可或缺的一部分,然而,很多时候,我们可能会遇到视频文件过大,无法在某些平台上传或保存的问题。那么,如何将过大的视频文件压缩变小呢? 下面就给大家分享三款实用的工具&…...
Edge 无法登录/同步问题【一招搞定】
目录 前言 一、打开 Edge 浏览器显示未同步,点击同步无效 二、Edge 登录报错 0x801901f4 或 0x80190001 解决方法 2.1 报错 0x801901f4 解决方法 2.1.0 Edge 登陆报错图示 2.1.1 添加 Edge 推荐的 DNS 地址 2.1.2 重新登录 Edge 账号成功 2.2 报错 0x801…...
ESP32-S3上手开发
1、搭建开发环境 首先搭建开发环境,这里采用了windows下集成开发环境ide进行开发,具体的安装方法:ESP-IDF安装配置 这里使用的乐鑫的esp32s3,N16R8 2、esp32s3模块 从上面图中可以看到,N16R8这里使用了外扩16M的fl…...
UE4和C++ 开发-编程基础记录(UE4+代码基础知识)
1、UE4基础元素 ①Actor 我们又见面了Actor,Actor是在一个关卡中持续存在的,通常他包含几个Actor组件。支持网络复制和多人游戏。 Actor不包含位置,方向。这些东西在Root Component中存储。对于UE3 中的Pawn也由PlayerCharacter继承了…...
【Unity】【VR】如何让Distance Grab抓取物品时限制物品的Rotation
【背景】 遇到这样的场景,希望抓取Canvas时,Canvas不会沿Z轴旋转。 【问题】 发现Freeze Canvas的Rigid Body没有用。 【分析】 应该是RigidBody的限制仅在物理互动下生效,抓取可能不属于物理互动(比如碰撞),所以不生效。 【思路】 还是得写脚本挂载在Interacta…...
为什么3ds max渲染效果图有噪点?点进来,CG Magic告诉您!
大家在使用3ds max渲染效果图时,可能渲染结果往往会出现的都是不真实,有小伙伴会问如何使3dmax渲染效果图真实呢? 不真实就算了,渲染过程中,会出现3Dmax渲染噪点多这类问题。 什么原因3ds max渲染效果图有噪点呢&a…...
Element UI怎么安装呢?
安装 :::warning 注意 后续演示将会在 Vue CLI 搭建的 Vue 项目上进行操作。如需要请查看 Vue CLI 安装 ::: 通过 YARN 命令安装 $ yarn add element-ui完整引入 代表一次性引入所有组件,比较省心省事,但是项目的打包体积也会跟着变大。 // main.js…...
redis批量删除命令
./redis-cli -h 127.0.0.1 -p 6379 -n 2 KEYS "170*:redisKeyStr" | xargs ./redis-cli -h 127.0.0.1 -p 6379 -n 2 DEL...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...














