1437 - 合并二叉树

通过次数

2

提交次数

2

时间限制 : 1 秒
内存限制 : 128 MB

给你两棵二叉树: root1root2

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

以层序遍历输出合并后的二叉树,空节点输出为null。

输入

第一行为2个整数nm,分别为root1root2的元素数量

第二行为n个整数,表示root1的元素,-10001表示空元素

第三行为m个整数,表示root2的元素,-10001表示空元素

输出

以层序遍历输出合并后的二叉树,空节点输出为null

样例

输入

4 7
1 3 2 5
2 1 3 -10001 4 -10001 7

输出

3 4 5 5 4 null 7

提示

  • 两棵树中的节点数目在范围 [0, 2000]

  • -10^4 <= Node.val <= 10^4