代码随想录阅读笔记-二叉树【合并二叉树】

题目

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

617.合并二叉树

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

思路 

相信这道题目很多人疑惑的点是如何同时遍历两个二叉树呢?

其实和遍历一个树逻辑是一样的,只不过传入两个树的节点,同时操作。

同样是递归和迭代两种思路

递归

二叉树使用递归,就要想使用前中后哪种遍历方式?

本题使用哪种遍历都是可以的!

我们下面以前序遍历为例。

动画如下:

617.合并二叉树

那么我们来按照递归三部曲来解决:

1、确定递归函数的参数和返回值:

首先要合入两个二叉树,那么参数至少是要传入两个二叉树的根节点,返回值就是合并之后二叉树的根节点。

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

2、确定终止条件:

因为是传入了两个树,那么就有两个树遍历的节点t1 和 t2,如果t1 == NULL 了,两个树合并就应该是 t2 了(如果t2也为NULL也无所谓,合并之后就是NULL)。

反过来如果t2 == NULL,那么两个数合并就是t1(如果t1也为NULL也无所谓,合并之后就是NULL)。

if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2
if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1

3、确定单层递归的逻辑:

单层递归的逻辑就比较好写了,这里我们重复利用一下t1这个树,t1就是合并之后树的根节点(就是修改了原来树的结构)。

那么单层递归中,就要把两棵树的元素加到一起。

t1->val += t2->val;

接下来t1 的左子树是:合并 t1左子树 t2左子树之后的左子树。

t1 的右子树:是 合并 t1右子树 t2右子树之后的右子树。

最终t1就是合并之后的根节点。

代码如下:

t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
return t1;

此时前序遍历,完整代码就写出来了,如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->val += t2->val;                             // 中
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        return t1;
    }
};

那么中序遍历也是可以的,代码如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->val += t2->val;                             // 中
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        return t1;
    }
};

后序遍历依然可以,代码如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        t1->val += t2->val;                             // 中
        return t1;
    }
};

但是前序遍历是最好理解的,我建议大家用前序遍历来做就OK。

如上的方法修改了t1的结构,当然也可以不修改t1和t2的结构,重新定义一个树。

不修改输入树的结构,前序遍历,代码如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        // 重新定义新的节点,不修改原有两个树的结构
        TreeNode* root = new TreeNode(0);
        root->val = t1->val + t2->val;
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};
迭代法

使用迭代法,如何同时处理两棵树呢?

思路我们在对称二叉树中的迭代法已经讲过一次了,求二叉树对称的时候就是把两个树的节点同时加入队列进行比较。

本题我们也使用队列,模拟的层序遍历,代码如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空,val相加
            node1->val += node2->val;

            // 如果两棵树左节点都不为空,加入队列
            if (node1->left != NULL && node2->left != NULL) {
                que.push(node1->left);
                que.push(node2->left);
            }
            // 如果两棵树右节点都不为空,加入队列
            if (node1->right != NULL && node2->right != NULL) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 当t1的左节点 为空 t2左节点不为空,就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空,就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }
        }
        return t1;
    }
};

原文中作者还拓展了一种单纯用指针的方式,大家可以参考学习。

如下代码中,想要更改二叉树的值,应该传入指向指针的指针。

代码如下:(前序遍历)

class Solution {
public:
    void process(TreeNode** t1, TreeNode** t2) {
        if ((*t1) == NULL && (*t2) == NULL) return;
        if ((*t1) != NULL && (*t2) != NULL) {
            (*t1)->val += (*t2)->val;
        }
        if ((*t1) == NULL && (*t2) != NULL) {
            *t1 = *t2;
            return;
        }
        if ((*t1) != NULL && (*t2) == NULL) {
            return;
        }
        process(&((*t1)->left), &((*t2)->left));
        process(&((*t1)->right), &((*t2)->right));
    }
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        process(&t1, &t2);
        return t1;
    }
};

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

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

相关文章

基于单片机的汽车尾灯控制系统设计

**单片机设计介绍&#xff0c;基于单片机的汽车尾灯控制系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的汽车尾灯控制系统设计概要主要涵盖利用单片机技术实现对汽车尾灯的智能控制。下面将从系统构成、工作…

2024年MathorCup数学建模思路A题思路解析+参考成品

1 赛题思路 (赛题出来以后第一时间在群内分享&#xff0c;点击下方群名片即可加群) 2 比赛日期和时间 报名截止时间&#xff1a;2024年4月11日&#xff08;周四&#xff09;12:00 比赛开始时间&#xff1a;2024年4月12日&#xff08;周五&#xff09;8:00 比赛结束时间&…

使用PostgreSQL中的隐式转换解决,MybatisPlus插入数据库时的类型不一致的问题

使用PostgreSQL中的隐式转换解决,MybatisPlus插入数据库时的类型不一致的问题 问题描述 鄙人在使用 MybatisPlus插件开发一个SpringBoot项目时, 遇到数据库中employee表与Java实体对象中某个属性的类型不一致, 导致插入数据库失败. 具体问题截图如下: 具体原因在于, Java实体…

用Excel画差异代谢物和差异表达基因的共富集图

◆ 背 景 ◆ 多组学策略已成为生物研究中的一种重要手段&#xff0c;从多个层次解析表型变化的内在机制。其中&#xff0c;转录组代谢组是应用最广泛的&#xff0c;寻找差异积累代谢物&#xff08;DAMs&#xff09;和差异表达基因&#xff08;DEGs&#xff09;的共富集…

Jmeter的使用

Jmeter的使用 1.Jmeter简介 以下内容来自Jmeter中文网http://www.jmeter.com.cn/jieshao&#xff0c;很好的解释了Jmeter的作用&#xff1a; Apache JMeter是Apache组织开发的基于Java的压力测试工具。用于对软件做压力测试&#xff0c;它最初被设计用于Web应用测试&#xf…

C#.net6.0手术麻醉信息管理系统源码,智慧手术室管理平台源码

手术麻醉信息管理系统源码&#xff0c;自主版权的手麻系统源码 手术麻醉信息管理系统包含了患者从预约申请手术到术前、术中、术后的流程控制。手术麻醉信息管理系统主要是由监护设备数据采集子系统和麻醉临床系统两个子部分组成。包括从手术申请到手术分配&#xff0c;再到术前…

Spring MVC 的执行流程

Spring MVC 的执行流程 1、用户输入 URL 或 点击链接&#xff0c;浏览器将发送 HTTP 请求到服务器 2、请求首先到达 Spring MVC 的前端控制器 DispatcherServlet 3、前端控制器通过处理器映射器 HandlerMapping 根据请求 URL 找到对应的处理器 handler 4、前端控制器使用处理…

中间件复习之-RPC框架

什么是RPC框架&#xff1f; RPC(Remote Procedure Call):远程过程调用。当多个应用部署在多个服务器上时&#xff0c;由于他们不在一个内存空间上&#xff0c;因此需要网络来进行通信&#xff0c;而RPC允许它像调用本地方法一样调用远程服务。 RPC原理 服务消费方通过RPC客户…

AWS上面部署一台jenkins

问题 客户预算有限&#xff0c;需要在aws云上面搞一台EC2手动安装jenkins发版。 步骤 创建密钥对 在EC2服务里面创建密钥对&#xff0c;具体如下图&#xff1a; 设置密钥对&#xff0c;如下图&#xff1a; 保存好这个私钥文件&#xff0c;以便后续用这个私钥文件ssh登录j…

RisingWave 在品高股份 Bingo IAM 中的应用

背景介绍 公司背景 品高股份&#xff0c;是国内专业的云计算及行业信息化服务提供商。公司成立于 2003 年&#xff0c;总部位于广州&#xff0c;下设多家子公司和分公司&#xff0c;目前员工总数近 900 人&#xff0c;其中 80 %以上是专业技术人员。 品高股份在 2008 年便开…

25.11 MySQL 视图

1. 常见的数据库对象 对象描述表(TABLE)存储数据的逻辑单元, 以行和列的形式存在, 列就是字段, 行就是记录.数据字典系统表, 存放数据库相关信息的表. 数据通常由数据库系统维护, 程序员通常不可修改, 只可查看.约束(CONSTRAINT)执行数据校验的规则, 用于保证数据完整性的规则…

JMeter+Grafana+influxdb 配置出现transaction无数据情况解决办法

JMeterGrafanainfluxdb 配置出现transaction无数据情况解决办法 一、问题描述二、解决方法 一、问题描述 如下图所示出现application有数据但是transaction无数据情况 二、解决方法 需要做如下设置 打开变量设置如下图打开两个选项 然后再进行后端监听器的设置 如下图所…

AR/VR技术对制造业劳动力危机的影响

借助 AR/VR 的力量缩小现代制造业的技能差距 数字化转型仍然是企业的首要任务&#xff0c;其许多方面都需要人工干预。然而&#xff0c;推动此类举措所需的技术工人日益短缺。这就造成了我们所说的“制造业劳动力危机”。 制造业应当如何&#xff1a; 制造业用工危机正在影响…

基于单片机的汽车自动预警刹车系统汇编

**单片机设计介绍&#xff0c;基于单片机的汽车自动预警刹车系统汇编 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的汽车自动预警刹车系统汇编概要主要描述了通过单片机技术实现汽车自动预警和刹车控制的系统设计和…

Tinymce富文本编辑器二次开发电子病历时解决的bug

前言 本文是在Tinymce富文本编辑器添加自定义toolbar&#xff0c;二级菜单&#xff0c;自定义表单&#xff0c;签名的基础之上进行一些bug记录&#xff0c;功能添加&#xff0c;以及模版的应用和打印 项目描述 建立电子病历模版—录入&#xff08;电子病历模版和电子病历打印…

微信小程序使用icon图标

原因&#xff1a; 微信小程序使用fontawesome库使用icon图标&#xff0c;网上有很多教程&#xff0c;按照网上说法制作&#xff0c;引入到微信小程序中&#xff0c;但是验证成功&#xff0c;只能使用部分图标&#xff0c;结果不尽如人意。后面使用阿里巴巴开源iconfont来使用ic…

【.NET全栈】ZedGraph图表库的介绍和应用

文章目录 一、ZedGraph介绍ZedGraph的特点ZedGraph的缺点使用注意事项 二、ZedGraph官网三、ZedGraph的应用四、ZedGraph的高端应用五、、总结 一、ZedGraph介绍 ZedGraph 是一个用于绘制图表和图形的开源.NET图表库。它提供了丰富的功能和灵活性&#xff0c;可以用于创建各种…

R语言数据挖掘:随机森林(1)

数据集heart_learning.csv与heart_test.csv是关于心脏病的数据集&#xff0c;heart_learning.csv是训练数据集&#xff0c;heart_test.csv是测试数据集。要求&#xff1a;target和target2为因变量&#xff0c;其他诸变量为自变量。用决策树模型对target和target2做预测&#xf…

使用Java拓展本地开源大模型的网络搜索问答能力

背景 开源大模型通常不具备最新语料的问答能力。因此需要外部插件的拓展&#xff0c;目前主流的langChain框架已经集成了网络搜索的能力。但是作为一个倔强的Java程序员&#xff0c;还是想要用Java去实现。 注册SerpAPI Serpapi 提供了多种搜索引擎的搜索API接口。 访问 Ser…

Unity性能优化篇(十四) 其他优化细节以及UPR优化分析器

代码优化&#xff1a; 1. 使用AssetBundle作为资源加载方案。 而且经常一起使用的资源可以打在同一个AssetBundle包中。尽量避免同一个资源被打包进多个AB包中。压缩方式尽量使用LZ4&#xff0c;少用或不要用LZMA的压缩方式。如果确定后续开发不会升级Unity版本&#xff0c;则可…