Problem
You are given a positive integer n
representing the number of nodes in a tree, numbered from 0
to n - 1
(inclusive). You are also given a 2D integer array edges
of length n - 1
, where edges[i] = [node1i, node2i]
denotes that there is a bidirectional edge connecting node1i
and node2i
in the tree.
You are given a 0-indexed integer array query
of length m
where query[i] = [starti, endi, nodei]
means that for the ith
query, you are tasked with finding the node on the path from starti
to endi
that is closest to nodei
.
Return an integer arrayanswer
of lengthm
, whereanswer[i]
is the answer to theith
query.
Examples
Example 1:
|
|
Example 2:
|
|
Example 3:
|
|
Constraints:
1 <= n <= 1000
edges.length == n - 1
edges[i].length == 2
0 <= node1i, node2i <= n - 1
node1i != node2i
1 <= query.length <= 1000
query[i].length == 3
0 <= starti, endi, nodei <= n - 1
- The graph is a tree.
Solution
Method 1 – BFS Preprocessing + Path Extraction
Intuition
To efficiently answer multiple queries, we precompute the shortest distances from every node to every other node using BFS. For each query, extract the path from start to end, then for each node on the path, find the one closest to the target node.
Approach
- Build the tree as an adjacency list.
- For each node, run BFS to compute the shortest distance to all other nodes (O(n^2) preprocessing).
- For each query
[start, end, node]
:- Extract the path from start to end using parent pointers from BFS.
- For each node on the path, compute its distance to node.
- Return the node on the path with the smallest distance to node (if tie, return the smallest index).
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity: O(n^2 + m * n), where n is the number of nodes and m is the number of queries.
- 🧺 Space complexity: O(n^2)