给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
深度优先搜索：
- 退出条件：两树的结点，有一个为 None 。
- 递推工作：合并左子树 left，合并右子树 right 。
- 返回值：新结点 new_node 。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if not root1: return root2
if not root2: return root1
left = self.mergeTrees(root1.left, root2.left)
right = self.mergeTrees(root1.right, root2.right)
new_node = TreeNode(root1.val + root2.val, left, right)
return new_node
- 时间复杂度 O(min(m, n))：其中 m，n 分别为树 root1 和树 root2 的结点数。
- 空间复杂度 O(min(m, n)：其中 m，n 分别为树 root1 和树 root2 的结点数。最差情况，树退化为链表，此时树的高度 == 结点数。