#P3844. 第1题-组织架构管理系统
-
1000ms
Tried: 441
Accepted: 117
Difficulty: 4
所属公司 :
华为
时间 :2025年9月28日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>树结构最近公共祖先
第1题-组织架构管理系统
解题思路
- 公司组织被简化为一棵二叉树,结点表示员工,父结点是上级,父结点“管理”其整棵子树的所有员工。
- 输入给出按层序(完全二叉树下标方式)展开的数组,
-1表示该位置没有员工;再给出两名员工工号u、v。 - 要求:找到两人级别最低的共同主管,并返回该主管子树中的员工总数(不含主管本人)。
核心做法:
-
数组建树 + 反向索引 用数组存树,建立“工号 → 数组下标”的映射。下标
i的父结点是(i-1)//2,左右子为2*i+1, 2*i+2(越界或值为-1视为不存在)。 -
LCA(最低公共祖先)
- 只在“下标树”上移动即可,无需真正建链表结构。
- 先把较深的下标逐级提升到同一深度,再同时向上移动直到相遇,得到 LCA 下标。
-
子树规模统计 从 LCA 下标出发做 DFS/栈遍历,统计其子树中非
-1结点数sz;答案为sz - 1(不计主管本人)。
为什么可行:数组层序就是完全二叉树的下标体系,父子关系由下标公式唯一确定;LCA 的“抬高再同步上跳”对任意树都成立;子树统计只需跳过越界和 -1。
复杂度分析
- 设数组长度为
n。 - 建立映射:
O(n); - LCA:每次上跳一步,最坏
O(h),h ≤ ⌊log2(n)⌋ + 1; - 子树统计:访问每个存在的结点一次,
O(n)(但仅遍历 LCA 子树,实际更小)。 - 时间复杂度:
O(n);空间复杂度:O(n)(映射与递归/栈深度)。
代码实现
Python
# -*- coding: utf-8 -*-
# 题意:数组表示的二叉树中,求两员工的最低共同主管,并返回其子树人数(不含主管)
import sys
def depth_idx(i: int) -> int:
"""计算数组下标 i 的深度(根为 0 层)"""
d = 0
while i > 0:
i = (i - 1) // 2
d += 1
return d
def lca_index(i: int, j: int) -> int:
"""在数组树中求下标 i 和 j 的 LCA 下标"""
di, dj = depth_idx(i), depth_idx(j)
# 先把较深者抬到同一深度
while di > dj:
i = (i - 1) // 2
di -= 1
while dj > di:
j = (j - 1) // 2
dj -= 1
# 同步向上直到相遇
while i != j:
i = (i - 1) // 2
j = (j - 1) // 2
return i
def subtree_size(arr, n, root_idx: int) -> int:
"""统计以 root_idx 为根的子树结点数(包含根,跳过 -1 和越界)"""
# 用显式栈避免递归深度问题
if root_idx >= n or arr[root_idx] == -1:
return 0
stack = [root_idx]
cnt = 0
while stack:
u = stack.pop()
if u >= n or arr[u] == -1:
continue
cnt += 1
l = 2 * u + 1
r = 2 * u + 2
if l < n:
stack.append(l)
if r < n:
stack.append(r)
return cnt
def solve():
data = sys.stdin.read().strip().split()
# 输入:n,接着 n 个整数的层序数组,最后两个工号
n = int(data[0])
arr = list(map(int, data[1:1 + n]))
u, v = map(int, data[1 + n:1 + n + 2])
# 建立工号到下标的映射
pos = {}
for i, x in enumerate(arr):
if x != -1:
pos[x] = i
iu = pos[u]
iv = pos[v]
# 求 LCA 下标
p = lca_index(iu, iv)
# 统计子树规模,答案不含主管本人
ans = subtree_size(arr, n, p) - 1
print(ans)
if __name__ == "__main__":
solve()
Java
// 请使用 Java 17+ 编译运行
// 功能:数组形式的二叉树中,求两员工的最低共同主管并统计其子树人数(不含主管)
import java.io.*;
import java.util.*;
public class Main {
static int n;
static long[] a; // 用 long 存工号,-1 表示不存在
static HashMap<Long, Integer> pos = new HashMap<>();
// 计算下标深度(根深度为 0)
static int depth(int i) {
int d = 0;
while (i > 0) {
i = (i - 1) / 2;
d++;
}
return d;
}
// 下标 LCA
static int lcaIndex(int i, int j) {
int di = depth(i), dj = depth(j);
while (di > dj) { i = (i - 1) / 2; di--; }
while (dj > di) { j = (j - 1) / 2; dj--; }
while (i != j) {
i = (i - 1) / 2;
j = (j - 1) / 2;
}
return i;
}
// 统计以 rootIdx 为根的子树大小(包含根;跳过 -1 和越界)
static int subtreeSize(int rootIdx) {
if (rootIdx >= n || a[rootIdx] == -1) return 0;
Deque<Integer> st = new ArrayDeque<>();
st.push(rootIdx);
int cnt = 0;
while (!st.isEmpty()) {
int u = st.pop();
if (u >= n || a[u] == -1) continue;
cnt++;
int l = 2 * u + 1, r = 2 * u + 2;
if (l < n) st.push(l);
if (r < n) st.push(r);
}
return cnt;
}
public static void main(String[] args) throws Exception {
// 读入:n,接着 n 个整数(层序数组),接着两个工号
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s1 = br.readLine();
n = Integer.parseInt(s1.trim());
String s2 = br.readLine();
StringTokenizer st = new StringTokenizer(s2);
a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = Long.parseLong(st.nextToken());
}
String s3 = br.readLine();
StringTokenizer st3 = new StringTokenizer(s3);
long u = Long.parseLong(st3.nextToken());
long v = Long.parseLong(st3.nextToken());
// 建立工号到下标的映射
for (int i = 0; i < n; i++) {
if (a[i] != -1) pos.put(a[i], i);
}
int iu = pos.get(u);
int iv = pos.get(v);
int p = lcaIndex(iu, iv);
int ans = subtreeSize(p) - 1; // 不含主管自身
System.out.println(ans);
}
}
C++
// 功能:数组表示的二叉树中,求两员工的最低共同主管,并输出其子树人数(不含主管)
#include <bits/stdc++.h>
using namespace std;
int depthIdx(int i) {
int d = 0;
while (i > 0) { i = (i - 1) / 2; ++d; }
return d;
}
int lcaIndex(int i, int j) {
int di = depthIdx(i), dj = depthIdx(j);
while (di > dj) { i = (i - 1) / 2; --di; }
while (dj > di) { j = (j - 1) / 2; --dj; }
while (i != j) { i = (i - 1) / 2; j = (j - 1) / 2; }
return i;
}
int subtreeSize(const vector<long long>& a, int n, int rootIdx) {
if (rootIdx >= n || a[rootIdx] == -1) return 0;
int cnt = 0;
vector<int> st; st.push_back(rootIdx);
while (!st.empty()) {
int u = st.back(); st.pop_back();
if (u >= n || a[u] == -1) continue;
++cnt;
int l = 2 * u + 1, r = 2 * u + 2;
if (l < n) st.push_back(l);
if (r < n) st.push_back(r);
}
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<long long> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
long long u, v; cin >> u >> v;
// 建立工号到下标的映射
unordered_map<long long, int> pos;
pos.reserve(n * 2);
for (int i = 0; i < n; ++i) if (a[i] != -1) pos[a[i]] = i;
int iu = pos[u], iv = pos[v];
int p = lcaIndex(iu, iv);
int ans = subtreeSize(a, n, p) - 1; // 不含主管本人
cout << ans << "\n";
return 0;
}
题目内容
你正在开发一个企业的组织架构管理系统,公司的组织架构被 简化表示为一棵二叉树。树的每个节点代表一个员工,树的层级越低则级别越高,高级别作为主管,管辖其子树涉及的所有员工。
每个人有一个唯一的工号,工号以整数值表示,范围是 [0,109] 。
此管理系统需要提供一个统计能力,对任意两名员工,找到他们级别最低的共同主管,返回当前主管管辖的人员个数。
注意:
-
如果两名员工本身存在上下级关系,共同主管为级别较高的员工。
-
员工总数 <=105。
-
待检索员工的工号一定在给定的二叉树中,且两位员工工号不同。
输入描述
-
第一行为一个整数,表示输入的节点个数。
-
第二行为一行数字,由空格分割,每个数字表示一颗满一叉树各层从左到右的节点。值为员工工号,−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 。