解题思路

先用 $BFS$ 按层序序列建出两棵二叉树，注意只有非空节点才继续读取它的左右孩子。

合并时使用 $DFS$ 判断冲突：

当两个位置都有节点时，节点值必须相同，否则冲突，不能合并；

当某个位置为空时，可以直接接上另一棵树对应位置的子树；

题目内容

某公司用二叉树来管理服务，随着部门业务的调整，需要对服务进行合并以节约管理成本，部门主管将服务合并的任务下发给你，聪明的你决定写一段代码来帮你节约时间；具体要求为：

一、当两棵二叉树部分重叠，且其余节点不冲突，则重叠部分可以合并得到新的树，如下图所示（示例 $1$）：

• 树一：$a$ $b$ $c$ $d$ $null$ $e$ $f$ $null$ $null$ $null$ $null$ $g$
• 树二：$c$ $e$ $f$ $null$ $null$ $null$ $q$
• 合并后：$a$ $b$ $c$ $d$ $null$ $e$ $f$ $null$ $null$ $null$ $null$ $g$ $q$

树采用层序遍历（按行）+ 空节点表示空缺的方式表示；

二、如果两棵树的节点有冲突（部分子节点无法合并），则不可合并，如下图所示（示例 $2$）；

三、如果树 $1$ 可以往树 $2$ 合并，树 $2$ 也可往树 $1$ 合并 ，则采用树 $2$ 往树 $1$ 合并；

输入描述

输入是两棵树，用字符串表示，长度不超过 $2000$ 个字符，合并前树的节点不重名，$null$ 为特殊字符表示空节点，例如：

• $a$ $b$ $c$ $d$ $null$ $e$ $f$ $null$ $null$ $null$ $null$ $g$
• $c$ $e$ $f$ $null$ $null$ $null$ $q$

输出描述

如果可以合并，则返回合并后的树： $a$ $b$ $c$ $d$ $null$ $e$ $f$ $null$ $null$ $null$ $null$ $g$ $q$

如果不可合并，则输出 $0$

样例1

输入

a b c d null e f null null null null ff
c e f null null it

输出

0

说明

$c, e, f$ 三个节点完全重合, 但子节点 $ff$ 和 $it$ 冲突了

样例2

输入

a b c d null e f null null null null g
c e f null null null q

输出

a b c d null e f null null null null g q

说明

$c, e, f$ 三个节点完全重合, 且子节点 $g$ 和 $q$ 也不冲突, 可以合并

提示

1. 不用考虑两棵树同时为空的场景；
2. 合并前树的节点不重名，合并后可重名；合并方式为整棵合并的逻辑，并去除重合部分；