C++合并二叉树的思路与示例代码

前言

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

思路

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就是合并之后的根节点。

/**
 * 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==nullptr) return root2;
        if(root2==nullptr) return root1;

        // 修改了t1的数值和结构
        root1->val+=root2->val;
        root1->left=mergeTrees(root1->left,root2->left);
        root1->right=mergeTrees(root1->right,root2->right);

        return root1;
    }
};

附：新建一颗树

不破坏原有两颗树结构

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1&&!t2)
            return NULL;
        TreeNode* node=new TreeNode(0);
        node->val=(t1? t1->val:0)+(t2? t2->val:0);
        node->left=mergeTrees((t1? t1->left: NULL),(t2? t2->left:NULL));
        node->right=mergeTrees((t1? t1->right: NULL),(t2? t2->right : NULL));
        return node;
    }
};

总结

到此这篇关于C++合并二叉树的文章就介绍到这了,更多相关C++合并二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • c++二叉树的几种遍历算法

    1. 前序/中序/后序遍历(递归实现) 复制代码 代码如下: // 前序遍历void BT_PreOrder(BiTreePtr pNode){ if (!pNode)  return;    visit(pNode);   BT_PreOrder(pNode->left); BT_PreOrder(pNode->right);   }// 中序遍历void BT_PreOrder(BiTreePtr pNode){  if (!pNode)  return;     BT_PreOrder(

  • C++实现二叉树遍历序列的求解方法

    C++实现二叉树遍历序列的求解方法

    本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值.具体分析如下: 一.由遍历序列构造二叉树 如上图所示为一个二叉树,可知它的遍历序列分别为: 先序遍历:ABDECFG 中序遍历:DBEAFCG 后序遍历:DEBFGCA 我们需要知道的是,由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树:由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树:但是如果只知道先序序列和后序序列,则无法唯一确定一棵二叉树. 二.已知二叉树的先序序列和中序序列,求后序

  • C++ 遍历二叉树实例详解

    C++ 遍历二叉树实例详解

    C++ 遍历二叉树实例详解 2叉数又叫红黑树,关于2叉数的遍历问题,有很多,一般有三种常用遍历方法: (1)前序遍历(2)中序遍历(3)后续遍历 以下是经典示例: #include "stdafx.h" #include<stdio.h> #include<malloc.h> #include <math.h > #define MaxSize 20 typedef struct BiTNode { int data; struct BiTNode

  • C++ 数据结构完全二叉树的判断

    C++ 数据结构完全二叉树的判断

    C++ 数据结构完全二叉树的判断 完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第h层外,其他各层(1~h-1)的节点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树.完全二叉树由满二叉树而引起来的.对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树. 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树. 完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二

  • C++二叉树结构的建立与基本操作

    C++二叉树结构的建立与基本操作

    准备数据定义二叉树结构操作中需要用到的变量及数据等. 复制代码 代码如下: #define MAXLEN 20    //最大长度typedef char DATA;    //定义元素类型struct  CBTType                   //定义二叉树结点类型 { DATA data;           //元素数据  CBTType * left;    //左子树结点指针  CBTType * right;   //右子树结点指针 }; 定义二叉树结构数据元素的类型DA

  • C++实现二叉树基本操作详解

    树是一种重要的非线性数据结构,二叉树是树型结构的一种重要类型.本学年论文介绍了二叉树的定义,二叉树的存储结构,二叉树的相关术语,以此引入二叉树这一概念,为展开二叉树的基本操作做好理论铺垫.二叉树的基本操作主要包含以下几个模块:二叉树的遍历方法,计算二叉树的结点个数,计算二叉树的叶子结点个数,二叉树深度的求解等内容. 前序遍历(递归&非递归) 访问根节点 前序访问左子树 前序访问右子树 //前序非递归 void PrevOrder() { stack<Node*> s; Node *cu

  • C++非递归建立二叉树实例

    C++非递归建立二叉树实例

    本文实例讲述了C++非递归建立二叉树的方法.分享给大家供大家参考.具体分析如下: 思路: 设置一个标记变量flag并初始化为1. flag = 1表示现在需要创建当前结点的左孩子,2表示需要创建右孩子,3则表示当前结点的左右孩子都已经创建完毕,需要执行出栈操作,直到当前结点不是父结点的右孩子为止. 以先序创建如图所示二杈树: 实现代码: PBTree create() { char ch[20]; scanf("%s",ch); int len = strlen(ch); PBTree

  • C++合并二叉树的思路与示例代码

    C++合并二叉树的思路与示例代码

    前言 给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠.你需要将他们合并为一个新的二叉树.合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点. 示例 1: 思路 1.确定递归函数的参数和返回值: 首先那么要合入两个二叉树,那么参数至少是要传入两个二叉树的根节点,返回值就是合并之后二叉树的根节点. 代码如下: TreeNode* mergeTrees(TreeNode* t1, TreeNod

  • C++实现二叉树及堆的示例代码

    C++实现二叉树及堆的示例代码

    1 树 树是一种非线性数据结构,它是由n个有限结点组成的具有层次关系的集合.把它叫树是因为它是根朝上,叶子朝下的 来上图瞧瞧 1.1 树的相关名词 2 二叉树 2.1 二叉树的概念 一颗二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树. 如图所示: 二叉树有以下特点: 1.每个二叉树最多有两颗子树,所以二叉树不存在度为2的结点. 2.二叉树的子树有左右之分,其子树的顺序不能颠倒. 2.2 二叉树的性质 1.若规定根结点的层数为第一层,则一颗非空二叉树的

  • python 按照sheet合并多个Excel的示例代码(多个sheet)

    python 按照sheet合并多个Excel的示例代码(多个sheet)

    工作中会遇到这样的需求,有多个Excel的格式一样,都有多个sheet,且每个sheet的名字和格式一样,我们需要按照sheet 合并,就是说合并后的表的格式和合并钱的格式是一样的.A.B.C表格式如图 现在需要合并成下图: 我这次处理是保留第一个表的首行,其余的表的首行都不保留.因此结果会和上面有所不同,上面的是将所有的首行都保存 import xlrd,xlsxwriter #待合并excel allxls=["C:/xxx/xxx.xlsx", "C:/xxx/xxx.

  • Java实现合并多个PDF的示例代码

    这里合并用到了一个itext的包.使用maven直接导入依赖即可. <dependency> <groupId>com.lowagie</groupId> <artifactId>itext</artifactId> <version>2.1.7</version> </dependency> 这个是我写的一个utl工具类,里面还写了一个main方法,如果你有两个pdf,可以直接用main方法跑一下. impo

  • Java实现合并word文档的示例代码

    Java实现合并word文档的示例代码

    目录 说明 实现 1.首先定义好主文档 2.定义需要追加的文档 3. 代码实现 4. 成果展示 说明 在做项目中,遇到了一种情况,需要将一个小word文档的内容插入到一个大word(主文档)中. 实现 1.首先定义好主文档 在主文档需要插入小word文档的位置上添加一个书签,这个书签名字要记住,后面要用. 2.定义需要追加的文档 3. 代码实现 package com.test.word; import com.aspose.words.Body; import com.aspose.words

  • Vue实现递归组件的思路与示例代码

    Vue实现递归组件的思路与示例代码

    目录 前言 一.递归组件是什么? 二.Vue实现递归的核心思路 三.代码示例 1.父级 2.子级 3.实现效果 补充:递归组件的应用场景 总结 前言 在我们开发过程中,为了提高开发效率,降低开发难度,我们会直接使用组件库来实现,同时也衍生出了很多优秀的组件库,如:饿了么.蚂蚁.Iview.vant等等.但是有时这些组件库提供给我们的组件不满足我们的需求或者定制组件时成本太高,那么我们就要手动实现了. 一.递归组件是什么? 字面理解为层层递进最后归并到一起,它的特点就是层级分明. 例如饿了么组件库

  • 用PHP代替JS玩转DOM的思路及示例代码

    事情的起源比较简单,我需要把一个导航页的数据整理好写入数据库.一个比较直观的方法是对html文件进行分析,通用的方法是用php的正则表达式来匹配.但是这样做开发和维护都很困难,代码可读性非常差. 导航页的数据都是规则的排列在DOM树当中的,用JS可以用几个循环轻松的对其进行操作,而且JS需要依赖浏览器,操作数据库很困难.其实PHP就有现成的类库对DOM树种的节点进行增删改查操作,在此做一些笔记. 这里涉及到2个类 DOMDocument 和 DOMXPath. 其实思路比较明确,就是通过DOMD

  • 将DataTable转换成List&lt;T&gt;实现思路及示例代码

    前几天在工作中,遇到一个问题:需要将查询出来的DataTable数据源,转换成List<T>的泛型集合(已知T类型).第一反应,我想肯定要用到"泛型"(这不是废话吗?都说了要转换成List<T>泛型集合了),而且还要用到"反射"相关的.呵呵.很快,我就做出了一个小实例,测试通过.下面我将代码贴出来,分享给大家.代码都有详细的注释,读者朋友可以很清晰的看懂我的思路. 首先,这是我写的一个通用转换类,完成此类操作.也是实现这个功能最核心的部分:

  • PHP利用MySQL保存session的实现思路及示例代码

    实现环境: PHP 5.4.24 MySQL 5.6.19 OS X 10.9.4/Apache 2.2.26 一.代码 CREATE TABLE `session` ( `skey` char(32) CHARACTER SET ascii NOT NULL, `data` text COLLATE utf8mb4_bin, `expire` int(11) NOT NULL, PRIMARY KEY (`skey`), KEY `index_session_expire` (`expire`

  • js实现点小图看大图效果的思路及示例代码

    DOM:就是用JavaScript操作HTML节点. 知识点: 将HTML变成DOM树 看到HTML会画DOM树. 创建节点,添加节点,删除节点 varnodeObj = document.createElement("节点名"); //创建元素节点 document.createTextNode("文本"); //创建文本节点 父节点.appendChild(子节点); //把子节点添加到父节点下 父节点.removeChild(子节点); //获得节点 docu

随机推荐