← 返回 atlassian 的题目列表Smallest Department Covering Two Employees (LCA Variant on an Org Tree)
类型：online_judge
Problem: Smallest Department Covering Two Employees (LCA Variant)
A company's org structure is represented as a tree:
Internal nodes are departments.
Leaf nodes are employees.
A department node's subtree contains all sub-departments and employees under it.
Given the org tree and two employees e1 and e2, find the lowest-level (closest to leaves) department d such that both e1 and e2 belong to d's subtree.
In other words, return the smallest department that covers both employees.
Input
An org tree root.
Two employees e1, e2 (corresponding to two leaf nodes in the tree).
Output
Return a department node d such that:
both e1 and e2 are in d's subtree;
among all such departments, d is the lowest (i.e., its subtree is as small as possible).
Constraints / Assumptions
e1 and e2 both exist in the same tree.
e1 != e2.
The tree is a general tree (a department may have any number of children).
Examples
Org tree (node types in parentheses):
Company(dept)
Eng(dept)
Platform(dept)
Alice(employee)
Bob(employee)
Product(dept)
Carol(employee)
HR(dept)
Dave(employee)
Input: e1 = Alice, e2 = Bob
Output: Platform
Input: e1 = Alice, e2 = Carol
Output: Eng
Input: e1 = Alice, e2 = Dave
Output: Company
Scale (for implementation considerations)
Total nodes N: up to 1e5
Tree height H: up to 1e5 in the worst case (may be skewed)
Implement a function to answer the query and state its time and space complexity.
Example
Input
(org tree as described)\ne1=Alice\ne2=Bob
Output
Platform