A22857.二叉树叶结点的深度之和

普及-

官方

通过率：0%

时间限制：1.00s

内存限制：128MB

题目描述

时间限制：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

说明/提示

样例 $1$ ：

构造出的二叉树如图所示：

叶节点 $3$ 和根节点的距离为 $4$ ；
叶节点 $4$ 和根节点的距离为 $4$ ；
叶节点 $9$ 和根节点的距离为 $3$ ；
叶节点 $2$ 和根节点的距离为 $3$ ；
所有叶子节点和根节点的距离之和为 $4 + 4 + 3 + 3 = 14$ 。

样例 $2$ ：
给出的先序遍历和中序遍历无法构造出唯一的二叉树。

首页