23_合并二叉树

简介: 23_合并二叉树

617. 合并二叉树

给你两棵二叉树: root1root2

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

返回合并后的二叉树。

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

[思路]

递归

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

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

TreeNode merageTrees(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 {
    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 {
    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 {
    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 {
    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;
    }
}

本题使用前、中、后序遍历都可以。

若不改变t1的结构,当然也可以不修改t1和t2的结构,重新定义一个树。

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

class Solution {
  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 root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root2);
        stack.push(root1);
        while (!stack.isEmpty()) {
            TreeNode node1 = stack.pop();
            TreeNode node2 = stack.pop();
            node1.val += node2.val;
            if (node2.right != null && node1.right != null) {
                stack.push(node2.right);
                stack.push(node1.right);
            } else {
                if (node1.right == null) {
                    node1.right = node2.right;
                }
            }
            if (node2.left != null && node1.left != null) {
                stack.push(node2.left);
                stack.push(node1.left);
            } else {
                if (node1.left == null) {
                    node1.left = node2.left;
                }
            }
        }
        return root1;
    }
}
相关文章
|
7月前
|
数据采集 人工智能 JavaScript
Browser Use:40.7K Star!一句话让AI完全接管浏览器!自动规划完成任务,多标签页同时管理
Browser Use 是一款专为大语言模型设计的智能浏览器自动化工具,支持多标签页管理、视觉识别、内容提取等功能,并能记录和重复执行特定动作,适用于多种应用场景。
1762 21
Browser Use:40.7K Star!一句话让AI完全接管浏览器!自动规划完成任务,多标签页同时管理
|
存储 JSON 索引
一文让你彻底搞懂 Python 字典是怎么实现的
一文让你彻底搞懂 Python 字典是怎么实现的
384 13
|
机器学习/深度学习 数据采集 算法
智能交通信号控制:优化城市交通流
【10月更文挑战第2天】随着城市化进程加快,交通拥堵成为严峻挑战。智能交通信号控制(ITSC)通过集成现代信息技术、大数据分析和人工智能,实现了交通信号的动态优化,有效缓解了交通拥堵,提升了交通效率。其工作原理包括数据采集与处理、交通状态感知、流量预测及信号灯控制策略制定等环节。目前,ITSC已在多个城市应用并取得显著效果,如提升交通效率、减少拥堵和改善安全等。未来,ITSC将融合多模态数据、应用深度学习算法、实现区域协同控制,并与其他智能交通系统集成,为构建安全、高效、绿色的城市交通环境贡献力量。
|
运维 负载均衡 算法
“分布式基础概念”全面解析,让你秒懂分布式系统!【一】
该博客文章全面解析了分布式系统的基础概念,包括微服务架构、集群与分布式的区别、节点定义、远程调用、负载均衡、服务注册与发现、配置中心、服务熔断与降级以及API网关,帮助读者快速理解分布式系统的关键组成部分和工作原理。
“分布式基础概念”全面解析,让你秒懂分布式系统!【一】
|
API 调度 芯片
FreeRTOS 延时函数和软件定时器 详解
FreeRTOS 延时函数和软件定时器 详解
FreeRTOS 延时函数和软件定时器 详解
|
NoSQL Redis 数据库
Redis 常见面试问题 Redis持久化aof后台重写和写时复制
今天有个群里网友问,redis面试被问到aof 后台重写 写时复制,我尝试回答一下
629 109
|
数据安全/隐私保护
如何配置战斧指纹浏览器和IPXProxy海外代理IP?
通过代理IP,用户可以轻松绕过地域限制,访问全球范围内的网站和服务。特别是对于跨境用户来说,需要在目标市场投放广告,而代理IP能帮助实现精准投放,快速的提升品牌或者店铺的知名度。那如何在如何在战斧指纹浏览器中设置IPXProxy海外代理IP?
349 0
|
Dubbo IDE NoSQL
SpringBoot+Mybatis多模块(module)项目搭建教程
SpringBoot+Mybatis多模块(module)项目搭建教程
690 0
SpringBoot+Mybatis多模块(module)项目搭建教程
|
消息中间件 弹性计算 固态存储
256变4096:分库分表扩容如何实现平滑数据迁移?
本文作者就一个高德打车弹外订单系统进行了一次扩分库分表和数据库迁移。
256变4096:分库分表扩容如何实现平滑数据迁移?