合并二叉树

给定两个二叉树，把它们合并成一棵新二叉树。合并规则是：如果两个节点重叠，那么把它们的值相加作为合并后节点的新值；否则，非 null 的节点直接作为新树的节点。

约定

• 合并应从各自的根节点开始，按位置对应合并。
• 你可以复用其中一棵树的节点，也可以新建节点，最终返回合并后树的根。

输入

• root1、root2：两棵二叉树的根节点，节点数均在 [0, 1000] 范围内，节点值 [-10^4, 10^4]。

输出

合并后二叉树的根节点。

示例一

输入：

root1 = [1, 3, 2, 5]
root2 = [2, 1, 3, null, 4, null, 7]

输出：

[3, 4, 5, 5, 4, null, 7]

示例二

输入：

root1 = [1]
root2 = [1, 2]

输出：

[2, 2]

复杂度要求

• 时间 O(m)，m 为两树重叠的节点数（实际访问到的节点数）。
• 空间 O(m)，递归栈深度。