题目
难度：★★☆☆☆
类型：二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例
输入:
Tree 1 Tree 2
1 2
/ \ /
3 2 1 3
/ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \
5 4 7
注意: 合并必须从两个树的根节点开始。
解答
设计融合函数，融合两棵树：
如果输入的两棵树均为空，返回空即可，如果输入的两棵树只有一棵为空，返回非空树；
如果两棵树均不为空，首先融合当前结点，然后将左右子树融合后挂在当前结点上。
class Solution:
def mergeTrees(self, t1, t2):
if not t1: # 如果t1为空
return t2 # 返回t2
if not t2: # 如果t2为空
return t1 # 返回t1
root = TreeNode(t1.val + t2.val) # 获得当前结点
root.left = self.mergeTrees(t1.left, t2.left) # 融合左子树
root.right = self.mergeTrees(t1.right, t2.right) # 融合右子树
return root # 返回融合的树
这里有个更加高效的版本：
class Solution:
def mergeTrees(self, t1, t2):
if t1 and t2: # 如果输入的两个结点均不为空
t1.val += t2.val # 结点值相加
t1.left = self.mergeTrees(t1.left, t2.left) # 合并左子树
t1.right = self.mergeTrees(t1.right, t2.right) # 合并右子树
return t1 # 返回t1
return t1 or t2
如有疑问或建议，欢迎评论区留言~
