解题思路

• 公司组织被简化为一棵二叉树，结点表示员工，父结点是上级，父结点“管理”其整棵子树的所有员工。
• 输入给出按层序（完全二叉树下标方式）展开的数组，-1 表示该位置没有员工；再给出两名员工工号 u、v。
• 要求：找到两人级别最低的共同主管，并返回该主管子树中的员工总数（不含主管本人）。

核心做法：

1. 数组建树 + 反向索引

题目内容

你正在开发一个企业的组织架构管理系统，公司的组织架构被 简化表示为一棵二叉树。树的每个节点代表一个员工，树的层级越低则级别越高，高级别作为主管，管辖其子树涉及的所有员工。

每个人有一个唯一的工号，工号以整数值表示，范围是 $[0,10^9]$ 。

此管理系统需要提供一个统计能力，对任意两名员工，找到他们级别最低的共同主管，返回当前主管管辖的人员个数。

注意：

• 如果两名员工本身存在上下级关系，共同主管为级别较高的员工。

• 员工总数 $<= 10^5$。

• 待检索员工的工号一定在给定的二叉树中，且两位员工工号不同。

输入描述

• 第一行为一个整数，表示输入的节点个数。

• 第二行为一行数字，由空格分割，每个数字表示一颗满一叉树各层从左到右的节点。值为员工工号，$-1$ 代表该节点不存在。

例 $1$ $2$ $3$ $4$ $-1$ $5$ $-1$ $-1$ $6$ 可转化为下图的一又树，

• 第三行为两个数字，用空格分割，表示待检索的两名员工工号，例如：$5$ $1$ 。

输出描述

输出级别最低的共同主管管辖的人员总个数(不包括自身)。

样例1

输入

12
2 3 5 1 7 6 8 -1 -1 0 4 -1
0 3

输出

4

说明

$0$ 和 $3$ 存在上下级关系，共同主管为 $3$ ，管辖总人数为 $4$ 。

样例2

输入

9
1 2 3 4 -1 5 -1 -1 6
5 4

输出

5

说明

$5$ 和 $4$ 的共同主管为节点 $1$ ，管辖总人数为 $5$ 。