102555: [AtCoder]ABC255 F - Pre-order and In-order
Description
Score : $500$ points
Problem Statement
Consider a binary tree with $N$ vertices numbered $1, 2, \ldots, N$. Here, a binary tree is a rooted tree where each vertex has at most two children. Specifically, each vertex in a binary tree has at most one left child and at most one right child.
Determine whether there exists a binary tree rooted at Vertex $1$ satisfying the conditions below, and present such a tree if it exists.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $N$ is an integer.
- $(P_1, P_2, \ldots, P_N)$ is a permutation of $(1, 2, \ldots, N)$.
- $(I_1, I_2, \ldots, I_N)$ is a permutation of $(1, 2, \ldots, N)$.
Input
Input is given from Standard Input in the following format:
$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $I_1$ $I_2$ $\ldots$ $I_N$
Output
If there is no binary tree rooted at Vertex $1$ satisfying the conditions in Problem Statement, print $-1$.
Otherwise, print one such tree in $N$ lines as follows.
For each $i = 1, 2, \ldots, N$, the $i$-th line should contain $L_i$ and $R_i$, the indices of the left and right children of Vertex $i$, respectively.
Here, if Vertex $i$ has no left (right) child, $L_i$ ($R_i$) should be $0$.
If there are multiple binary trees rooted at Vertex $1$ satisfying the conditions, any of them will be accepted.
$L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$
Sample Input 1
6 1 3 5 6 4 2 3 5 1 4 6 2
Sample Output 1
3 6 0 0 0 5 0 0 0 0 4 2
The binary tree rooted at Vertex $1$ shown in the following image satisfies the conditions.
Sample Input 2
2 2 1 1 2
Sample Output 2
-1
No binary tree rooted at Vertex $1$ satisfies the conditions, so $-1$ should be printed.
Input
题意翻译
给定一棵二叉树的先序遍历和中序遍历,请构造一棵以 $ 1 $ 节点为根的二叉树。第 $ i $ 行输出节点 $ i $ 的左右儿子,儿子为空则输出 $ 0 $。无解输出 `-1`。Output
问题描述
考虑一个具有$N$个顶点的二叉树,顶点编号为$1, 2, \ldots, N$。这里,二叉树是一种有根树,其中每个顶点最多有两个子节点。具体来说,二叉树中的每个顶点最多有一个 左子节点 和一个 右子节点。
确定是否存在一个以顶点$1$为根的二叉树满足以下条件,并在存在时给出这样的树。
约束条件
- $2 \leq N \leq 2 \times 10^5$
- $N$ 是整数。
- $(P_1, P_2, \ldots, P_N)$ 是$(1, 2, \ldots, N)$的排列。
- $(I_1, I_2, \ldots, I_N)$ 是$(1, 2, \ldots, N)$的排列。
输入
输入从标准输入以以下格式给出:
$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $I_1$ $I_2$ $\ldots$ $I_N$
输出
如果不存在以顶点$1$为根的二叉树满足问题描述中的条件,则输出$-1$。
否则,按以下方式在$N$行中输出这样的树。
对于每个$i = 1, 2, \ldots, N$,第$i$行应包含$L_i$和$R_i$,即顶点$i$的左子节点和右子节点的索引。
如果顶点$i$没有左(右)子节点,则$L_i$($R_i$)应为$0$。
如果存在多个以顶点$1$为根的二叉树满足条件,任何其中之一都将被接受。
$L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$
样例输入 1
6 1 3 5 6 4 2 3 5 1 4 6 2
样例输出 1
3 6 0 0 0 5 0 0 0 0 4 2
以顶点$1$为根的二叉树如图所示满足条件。
样例输入 2
2 2 1 1 2
样例输出 2
-1
不存在以顶点$1$为根的二叉树满足条件,因此应输出$-1$。