leetcode原题链接：617. 合并二叉树
可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。
两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1: return t2
if not t2: return t1
merge = TreeNode(t1.val + t2.val)
merge.left = self.mergeTrees(t1.left, t2.left)
merge.right = self.mergeTrees(t1.right, t2.right)
return merge复杂度分析
时间复杂度：
O
(
min
(
m
,
n
)
)
O(\min(m,n))
O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作，因此被访问到的节点数不会超过较小的二叉树的节点数。
空间复杂度：
O
(
min
(
m
,
n
)
)
O(\min(m,n))
O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数，此时二叉树退化成链表。