可视化图解算法：合并二叉树

1. 题目

描述

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：

数据范围：树上节点数量满足 0 ≤n≤500，树上节点的值一定在32位整型范围内。

进阶：空间复杂度 O(1) ，时间复杂度 O(n)

示例1

输入：

{1,3,2,5},{2,1,3,#,4,#,7}

返回值：

{3,4,5,5,4,#,7}

示例2

输入：

{1},{}

返回值：

{1}

2. 解题思路

二叉树tree1与tree2的合并，我们可以将tree2合并到tree1，采用递归方法。具体操作为：

        tree1的节点值为两颗二叉树节点值的和：t1.val=t1.val+t2.val;

        tree1的新生成的左子树为：tree1的左子树和tree2的左子树合并的结果；

        tree1的新生成的右子树为：tree1的右子树和tree2的右子树合并的结果。

先来看看二叉树的合并是否满足递归条件：

可以看出，二叉树的合并满足递归的两个条件，因此可以通过递归来实现二叉树的合并。我们将tree2合并到tree1，采用递归方法。具体操作为：

        tree1的节点值为两颗二叉树节点值的和：t1.val=t1.val+t2.val;

        tree1的新生成的左子树为：tree1的左子树和tree2的左子树合并的结果；

        tree1的新生成的右子树为：tree1的右子树和tree2的右子树合并的结果。

对应的递推公式如下：

有了递推公式，就可以很方便的写出代码。tree1与tree2合并之后，新生成的二叉树如下所示：

如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python版本：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372109

• Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367348

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364773

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param t1 TreeNode类* @param t2 TreeNode类* @return TreeNode类*/
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {// write code here// 2. 递归终止条件if t1 == nil && t2 == nil {return nil}// 2.2 当前节点为空，则返回另外一个节点if t1 == nil && t2 != nil {return t2}if t1 != nil && t2 == nil {return t1}// 1. 问题分解（递推公式）// 1.1 root节点处理（将t2合并到t1）,两个节点的值求和并赋给t1t1.Val = t1.Val + t2.Val// 1.2 合并t1、t2的左节点t1.Left = mergeTrees(t1.Left, t2.Left)// 1.3 合并t1、t2的右节点t1.Right = mergeTrees(t1.Right, t2.Right)return t1
}

• Python版本：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372109

• Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367348

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364773

4.小结

二叉树tree1与tree2的合并，我们可以将tree2合并到tree1，采用递归方法。具体操作为：

        tree1的节点值为两颗二叉树节点值的和：t1.val=t1.val+t2.val;

        tree1的新生成的左子树为：tree1的左子树和tree2的左子树合并的结果；

        tree1的新生成的右子树为：tree1的右子树和tree2的右子树合并的结果。

《数据结构与算法》深度精讲课程正式上线啦！七大核心算法模块全解析：

        ✅  链表

        ✅  二叉树

        ✅  二分查找、排序

        ✅  堆、栈、队列

        ✅  回溯算法

        ✅  哈希算法

        ✅  动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss63997

对于二叉树的相关算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：十年身事各如萍，白首相逢泪满缨。