KK与二叉树

Tags:

Description

OJ的栈空间大小为128MB，能够保证本题在一条链的情况下递归下去不会爆栈

众所周知，先序遍历序列和中序遍历序列可以唯一的确定一棵二叉树，或者后序遍历序列和中序遍历序列也可以唯一的确定一棵二叉树。

不幸的是，先序遍历序列和后序遍历序列却不一定能够唯一的确定一棵二叉树。
更不幸的是，现在KK得到了一个先序遍历序列和一个后序遍历序列，它想知道这个先序遍历序列和后序遍历序列能否唯一的确定一棵二叉树。

• 如果能够唯一确定一棵二叉树，那么你需要输出该二叉树的中序遍历序列。
• 如果不能够唯一确定一棵二叉树，那么输出所有可能的二叉树的中序遍历序列结果中字典序最小的一个。

Input

多组数据评测。 
第一行一个正整数$T(1 \leq T \leq 10^5)$，表示数据组数。
对于每组数据：
第一行一个正整数$n(1 \leq n \leq 10^5)$，表示二叉树的结点个数。
第二行$n$个互不相同的正整数$a_i(1 \leq a_i \leq 10^9)$, 表示该二叉树的先序遍历序列。
第三行$n$个互不相同的正整数$b_i(1 \leq b_i \leq 10^9)$, 表示该二叉树的后序遍历序列。
数据保证$\sum n \leq 10^5$。

Output

输出包含$T$组，对于每一组数据：
如果给出的先序遍历序列和后序遍历序列能够唯一确定一棵二叉树：
第一行输出一个'Yes'(没有引号)。
第二行输出该二叉树的中序遍历序列。
否则：
第一行输出一个'No'(没有引号)。
第二行输出所有可能的二叉树的中序遍历序列结果中字典序最小的一个。

Samples

Hint

字典序: 
如果有两个长度相同(假定长度为$n$)的序列$a_i$和$b_i$，如果存在一个$x \in [1, n]$，满足
$$
\begin{eqnarray*}
a_1 = b_1, a_2 = b_2, \cdots, a_{x - 1} = b_{x - 1} \quad and \quad a_x < b_x
\end{eqnarray*}
$$
这两个条件，那么我们认为序列$a_i$的字典序比序列$b_i$的字典序要小。

二叉树：
二叉树是每个结点最多有两个子树的树结构。
如下图就是一个二叉树：

先序遍历序列(preorder traversal sequences)：
根据根左右的顺序沿一定路径经过路径上所有的结点得到的遍历序列。
遍历方法：
首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。
上图二叉树的先序遍历序列为：
$$
\begin{eqnarray*}
1\;2\;4\;5\;3\;6\;7
\end{eqnarray*}
$$
中序遍历序列(inorder traversal sequences)：
根据左根右的顺序沿一定路径经过路径上所有的结点得到的遍历序列。
遍历方法：
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回
上图二叉树的中序遍历序列为：
$$
\begin{eqnarray*}
4\;2\;5\;1\;6\;3\;7
\end{eqnarray*}
$$
后序遍历序列(postorder traversal sequences)：
根据左右根的顺序沿一定路径经过路径上所有的结点得到的遍历序列。
遍历方法：
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点，若二叉树为空则结束返回。
上图二叉树的后序遍历序列为：
$$
\begin{eqnarray*}
4\;5\;2\;6\;7\;3\;1
\end{eqnarray*}
$$

Author