( “树” 之 DFS) 617. 合并二叉树 ——【Leetcode每日一题】

news/2024/2/28 17:36:37

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-10^4 <= Node.val <= 10^4104<=Node.val<=104

思路:递归 DFS

1、首先要清楚我们要写的递归函数返回什么?

  • 这里的mergeTrees返回合并后的头结点

2、然后考虑边界,就是什么时候返回return,以及是否需要合并

  • 如果root1root2中有一个节点为空,则不需要合并,直接另外一个节点即可;
  • 如果都不空,则需要合并,可以将root2合并到root1,不用再申请新的节点;
  • 当前节点处理完,在递归处理左子树和右子树;
  • 返回合并后的头结点root1.

代码:(Java、C++)

Java

/*** 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 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;}
}

C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
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;}
};

运行结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度O(min⁡(m,n))O(min⁡(m,n))O(min(m,n)),其中 mn 分别是两个二叉树的节点个数。对两个二叉树同时进行深度优先搜索,只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作,因此被访问到的节点数不会超过较小的二叉树的节点数。

  • 空间复杂度O(min⁡(m,n))O(min⁡(m,n))O(min(m,n)),其中 mn 分别是两个二叉树的节点个数。空间复杂度取决于递归调用的层数,递归调用的层数不会超过较小的二叉树的最大高度,最坏情况下,二叉树的高度等于节点数。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/43278.html

相关文章

RabbitMQ 基础篇 | 黑马

目录 一、RabbitMQ简介 1、AMQP 2、基本概念 3、工作模式 4、JMS 5、小结 二、快速入门 简单模式 生产者 消费者 三、工作模式 1、Work queues 工作队列模式 2、Pub/Sub 订阅模式 3、Routing 路由模式 4、Topics 通配符模式 四、SpringBoot整合RabbitMQ 1、生产…

如何设计一个安全的对外接口?

对外接口安全措施的作用主要体现在两个方面&#xff0c;一方面是如何保证数据在传输过程中的安全性&#xff0c;另一方面是数据已经到达服务器端&#xff0c;服务器端如何识别数据。 1. 数据加密 数据在传输过程中是很容易被抓包的&#xff0c;如果直接传输&#xff0c;数据可…

HTML:彩虹按钮

彩虹按钮&#xff08;盗版按钮&#xff0c;B站仿写&#xff0c;略有不同&#xff01;&#xff09; 链接 <html><head><title>demo</title><style>*{margin: 0;padding: 0;}body{display: flex;justify-content: center;align-items: center;…

电脑上删除的文件可以恢复吗 如何恢复电脑上删除的文件

电脑早已走进千家万户&#xff0c;成为我们不可或缺的家庭设备&#xff0c;我们用电脑来学习、工作&#xff0c;处理各种数据。在使用电脑处理数据时&#xff0c;可能会失误操作&#xff0c;删除重要文件。那么&#xff0c;电脑上删除的文件可以恢复吗&#xff0c;如何恢复电脑…

Optional类快速上手

目录 一、概述 二、使用 1、创建对象 2、安全消费值 3、安全获取值 4、过滤 5、判断 6、数据转换 一、概述 我们在编码的时出现最多的就是空指针异常&#xff0c;所以在很多情况下我们需要做各种非空的判断。 尤其是对象中的属性还是一个对象的情况下&#xff0c;这种…

android ndk 编译 libevent

android ndk 编译 libevent Russinovichs Blog 2022-10-19 原文 https://www.shuzhiduo.com/A/rV57oAKG5P/ 下载 libevent 2.1.8 版本 https://github.com/libevent/libevent/releases/download/release-2.1.8-stable/libevent-2.1.8-stable.tar.gz 先在 win10 上用 wsl ubun…

【计算机网络-传输层】TCP 协议

文章目录1 传输层概述1.1 传输层的功能1.2 端口号2 TCP 报文段2.1 TCP 报文段首部格式2.2 TCP 数据传送的过程3 TCP 连接管理3.1 TCP 连接的建立——三次握手3.1.1 客户机向服务器发送 TCP 连接请求报文段3.1.2 服务器向客户机发送 TCP 连接请求确认报文段3.1.3 客户机向服务器…

数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)

目录 二叉树的定义 二叉树具体的五种基本形态 1.空树 2.只有一个节点 3.有左子树&#xff0c;但右子树为空 4.有右子树&#xff0c;但左子树为空 5.左右两子树都不为空 特殊二叉树 斜二叉树 满二叉树 完全二叉树 二叉树的几个重要性质 初识二叉树的几个操作函数 …

软件测试工作主要做什么

随着信息技术的发展和普及&#xff0c;人们对软件的使用越来越普及。但是在软件的使用过程中&#xff0c;软件的效果却不尽如人意。为了确保软件的质量&#xff0c;整个软件业界已经逐渐意识到测试的重要性&#xff0c;也有越来越多的小伙伴加入了软件测试这个行业中来。软件测…

Moonbeam操作指南 | 如何设置Moonbeam开发节点

Moonbeam开发节点是为本地构建和测试应用的个人开发环境。对以太坊开发者来说&#xff0c;可以和Ganache相媲美。可以使你快速上手&#xff0c;且无需中继链的支出即可轻松实现。 有2种方式可以开始运行节点&#xff1a;使用Docker运行一个预构建的二进制文件&#xff0c;或者…

光耦继电器工作原理及优点概述

光耦继电器是一种电子元器件&#xff0c;也是固态继电器的一种&#xff0c;其主要作用是隔离输入与输出电路&#xff0c;用于保护或者控制电路的正常工作。 光耦继电器工作原理是利用光电转换器将外界信号转化为光信号&#xff0c;通过光纤传输到另一端&#xff0c;再由另一端的…

C#使用EF框架连接SQLServer数据库

C#中使用Entity Framework (EF)连接SQL Server数据库可以使用多种方法&#xff0c;其中比较常用的是Code First和Database First两种方式。 Code First方式 Code First是指通过C#代码来定义数据模型&#xff0c;EF会根据代码自动生成数据库结构。使用Code First需要进行以下步…

JavaWeb开发 —— Web入门

目录 一、Spring 二、SpringBootWeb快速入门 三、HTTP协议 1. 概述 2. 请求协议 3. 响应协议 四、Web服务器 - Tomcat 1. 介绍 2. 基本使用 3. 入门程序解析 一、Spring ① 官网&#xff1a;http://spring.io ② Spring 发展到今天已经形成了一种开发生态圈&…

构建自动过程:FinalBuilder 8.0 Crack

使用 FinalBuilder 自动化您的构建过程很简单。使用 FinalBuilder&#xff0c;您无需编辑 xml 或编写脚本。可视化定义和调试您的构建脚本&#xff0c;然后使用 Windows 调度程序安排它们&#xff0c;或将它们与 Continua CI、Jenkins 或任何其他 CI 服务器集成。 成千上万的软…

MySQL5.5安装图解

一、MYSQL的安装 &#xff11;、打开下载的mysql安装文件mysql-5.5.27-win32.zip&#xff0c;双击解压缩&#xff0c;运行“setup.exe” &#xff12;、选择安装类型&#xff0c;有“Typical(默认)”、“Complete(完全)”、“Custom(用户自定义)”三个选项&#xff0c;选择“Cu…

爬虫1000+个C程序

爬虫1000个C程序 问题场景 由于实验需要&#xff0c;我需要1000个elf文件&#xff0c;可是网络可获取的elf文件较少&#xff0c;c程序较多&#xff0c;所以首先下载c程序&#xff0c;之后gcc编译链接生成elf文件。我需要的C源码不是项目级别的&#xff0c;正常100行左右就可以…

Rollup 实践:插件生态和实用技巧(续)

在前面的文章中&#xff0c;我们已经了解了 Rollup 的性能优化和高级用法。本篇文章将继续探讨 Rollup 的插件生态和实用技巧。 插件生态 Rollup 拥有一个丰富的插件生态&#xff0c;下面我们介绍几个实用的插件&#xff1a; rollup-plugin-terser&#xff1a;使用 Terser 压…

框架技巧03:gitHub检索技巧

01-背景介绍 在用了那么久框架之后&#xff0c;才忽然发现之间在github上搜索是关键字是多么无语&#xff0c;原来github上也是有技巧&#xff0c;可以更快获取到你想要信息 02-技巧介绍&#xff1a; 在GitHub上搜索时&#xff0c;使用一些特定的搜索技巧和过滤器可以帮助您…

解决macOS IntelliJ IDEA 卡顿问题

写在前面的话1&#xff1a;我在撰写这篇博客时候&#xff0c;所用的IntelliJ IDEA版本是IntelliJ IDEA 2022.3.3 (Ultimate Edition)&#xff0c;你需要知道可能对于不同的IntelliJ IDEA版本会有一定的差异 写在前面的话2&#xff1a;如果我这篇博客可以帮助到你&#xff0c;请…

TP5 解决如何实现生成并导出Word文档功能

今天连续更新两篇文章&#xff0c;上一篇讲了一下如何生成PDF并导出文件的功能 接下来我们就来拼一拼怎么实现生成并导出word文档的功能 话不多说 我们直接上流程&#xff1a; 1.下载安装phpword插件&#xff1a;composer require phpoffice/phpword 2.安装成功后该插件在我们项…
最新文章