Statement▼
You are given a positive integer, n, representing the number of nodes in a tree, numbered from edges of length edges[i]
You are also given a 2D integer array query of length query[i]
For each query i, find the node on the path between
Return an integer array where the value at index
Note: If there are multiple such nodes at the same minimum distance, return the one with the smallest index.
Constraints:
1≤ n≤1000 edges.length==n−1 edges[i].length==2 0≤ui,vi≤n−1 ui !=vi 1≤ query.length≤1000 query[i].length==3 0≤starti,endi,nodei≤n−1 The graph is a tree.
Solution
The solution’s essence lies in first determining the exact path between two nodes in a tree using breadth-first search (BFS), and then identifying which node along that path is closest to a third given node. To do this, we perform a second BFS from the third node to compute the shortest distance to all other nodes in the tree. Finally, by comparing these distances for each node on the path, we select the one with the minimum distance, breaking ties by choosing the smaller node index.
Using the intuition above, we implement the algorithm as follows:
Initialize a 2D array,
tree, to store the given tree as an adjacency list to represent node connections.For each edge
[u, v]inedges, addvtotree[u]andutotree[v]. This builds a bidirectional structure from the inputedges.Initialize an array,
answer, to store the answer to each query.For each query
[start, end, node]:Use BFS to find the path from
starttoend:Initialize an array,
parents, of sizenwith all entries as-1to keep track of each node’s parent.Create a queue and a
visitedarray to perform standard BFS.Push
startinto the queue and mark it as visited.For every dequeued node:
If it equals
end, break the loop.Otherwise, enqueue all unvisited neighbors, mark them visited in the
visitedarray, and record their parent in theparentsarray.
Reconstruct the path from
starttoend:Starting from
end, backtrack using theparentsarray until reachingstart.Collect all nodes along this path into a
patharray.Reverse the
pathto get the correct order fromstarttoend.
Use BFS again to calculate the shortest distance from the
nodeto all other nodes:Initialize a
distarray of sizen, all set to the maximum integer value.Set
dist[node] = 0and start BFS fromnode.For each dequeued node:
For all its unvisited neighbors (i.e.,
dist[v]is still at maximum integer value), setdist[v] = dist[u] + 1and enqueue them.
Identify the closest node on the path to
node:Initialize
minDistwith the maximum integer value andanswerNodewith-1.Traverse each node
pin thepath:If
dist[p]is less thanminDist, or if the distance is equal andpis smaller thananswerNode, update bothminDistandanswerNode.
Add
answerNodeto theanswerarray.
After processing all queries, return the
answerarray containing the closest node on each path.
Let’s look at the following illustration to get a better understanding of the solution: