← 返回比赛
已结束 GESP排位赛#8
← 上一题 下一题 →

A3029 | 二叉树叶结点的深度之和

来源官方 / 2024
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

时间限制：1000ms

内存限制：128MB


给定一个有 $N$ 个节点的二叉树的 $\bf{先序遍历}$ 结果 $A$ 和 $\bf{中序遍历}$ 结果 $B$，请你求出树中所有 $\bf{叶节点}$ 的 $\bf{深度}$ 之和。

$\bf{每个测试文件包含\ T\ 个测试用例。}$

$\large{数据范围}$

- $1 \le T \le 10$
- $1 \le N \le 1000$
- $1 \le A_i, B_i \le N$
- $A_i \ne A_j,\ B_i \ne B_j\ (i \ne j)$

输入格式

每个测试文件格式如下：
$\tt{T}$

$\tt{Testcase_1}$
$\tt{Testcase_2}$
$\tt{\vdots}$
$\tt{Testcase_T}$

对于每个 $\tt{Testcase}$ 格式如下：
$\tt{N}$

$\tt{A_1\ A_2\ A_3\ \cdots\ A_N}$
$\tt{B_1\ B_2\ B_3\ \cdots\ B_N}$

输出格式

对于每个 $\tt{Testcase}$ 若给出的先序遍历和中序遍历可以唯一地构造出一颗二叉树，输出所有叶子结点到根节点的距离之和，否则输出 $-1$。

输入输出样例

输入 #1
3
10
7 8 5 6 3 4 9 1 10 2
8 3 6 4 5 9 7 10 2 1
8
3 1 2 4 7 8 5 6
3 6 2 1 7 8 5 4
17
6 4 12 15 7 3 17 16 9 10 14 8 13 1 5 11 2
12 4 15 6 17 3 16 9 7 8 13 14 5 1 2 11 10
输出 #1
14
-1
27
C++ 编辑器
输入
输出