-1
表示该位置没有员工;再给出两名员工工号 u、v
。核心做法:
i
的父结点是 (i-1)//2
,左右子为 2*i+1, 2*i+2
(越界或值为 -1
视为不存在)。你正在开发一个企业的组织架构管理系统,公司的组织架构被 简化表示为一棵二叉树。树的每个节点代表一个员工,树的层级越低则级别越高,高级别作为主管,管辖其子树涉及的所有员工。
每个人有一个唯一的工号,工号以整数值表示,范围是 [0,109] 。
此管理系统需要提供一个统计能力,对任意两名员工,找到他们级别最低的共同主管,返回当前主管管辖的人员个数。
注意:
如果两名员工本身存在上下级关系,共同主管为级别较高的员工。
员工总数 <=105。
待检索员工的工号一定在给定的二叉树中,且两位员工工号不同。
第一行为一个整数,表示输入的节点个数。
第二行为一行数字,由空格分割,每个数字表示一颗满一叉树各层从左到右的节点。值为员工工号,−1 代表该节点不存在。
例 1 2 3 4 −1 5 −1 −1 6 可转化为下图的一又树,
输出级别最低的共同主管管辖的人员总个数(不包括自身)。
输入
12
2 3 5 1 7 6 8 -1 -1 0 4 -1
0 3
输出
4
说明
0 和 3 存在上下级关系,共同主管为 3 ,管辖总人数为 4 。
输入
9
1 2 3 4 -1 5 -1 -1 6
5 4
输出
5
说明
5 和 4 的共同主管为节点 1 ,管辖总人数为 5 。