2277

2277. Closest Node to Path in Tree (Hard)

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 array answer of length m, where answer[i] is the answer to the ith query.

 

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[0,3],[1,4],[2,5],[2,6]], query = [[5,3,4],[5,3,6]]
Output: [0,2]
Explanation:
The path from node 5 to node 3 consists of the nodes 5, 2, 0, and 3.
The distance between node 4 and node 0 is 2.
Node 0 is the node on the path closest to node 4, so the answer to the first query is 0.
The distance between node 6 and node 2 is 1.
Node 2 is the node on the path closest to node 6, so the answer to the second query is 2.

Example 2:

Input: n = 3, edges = [[0,1],[1,2]], query = [[0,1,2]]
Output: [1]
Explanation:
The path from node 0 to node 1 consists of the nodes 0, 1.
The distance between node 2 and node 1 is 1.
Node 1 is the node on the path closest to node 2, so the answer to the first query is 1.

Example 3:

Input: n = 3, edges = [[0,1],[1,2]], query = [[0,0,0]]
Output: [0]
Explanation:
The path from node 0 to node 0 consists of the node 0.
Since 0 is the only node on the path, the answer to the first query is 0.

 

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.

Companies: Google

Related Topics:
Array, Tree, Depth-First Search, Breadth-First Search

Similar Questions:

• Count Number of Possible Root Nodes (Hard)
• Design Graph With Shortest Path Calculator (Hard)

Hints:

• For the ith query, find the distance from node_i to every other node in the tree.
• We can use a BFS to find the distances.
• Use DFS to find all the nodes on the path from start_i to end_i.

Solution 1. Post-order traversal (Lowest Common Ancestor)

For each query, DFS from node to all other nodes. Find the first node (furthest from node) that is in both paths to start and end.

// OJ: https://leetcode.com/problems/closest-node-to-path-in-tree
// Author: github.com/lzl124631x
// Time: O(QN)
// Space: O(N)
class Solution {
public:
    vector<int> closestNode(int n, vector<vector<int>>& E, vector<vector<int>>& Q) {
        vector<vector<int>> G(n);
        for (auto &e: E) {
            int u = e[0], v = e[1];
            G[u].push_back(v);
            G[v].push_back(u);
        }
        vector<int> ans;
        for (auto &q : Q) {
            int start = q[0], end = q[1], node = q[2], r = -1;
            function<int(int, int)> dfs = [&](int u, int prev) {
                int cnt = 0;
                if (u == start) ++cnt;
                if (u == end) ++cnt;
                for (int v : G[u]) {
                    if (v == prev) continue;
                    cnt += dfs(v, u);
                }
                if (cnt == 2 && r == -1) r = u; // The first node that has both `start` and `end` as children or self is the LCA
                return cnt;
            };
            dfs(node, -1);
            ans.push_back(r);
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/closest-node-to-path-in-tree
// Author: github.com/lzl124631x
// Time: O(QN)
// Space: O(N)
class Solution {
public:
    vector<int> closestNode(int n, vector<vector<int>>& E, vector<vector<int>>& Q) {
        vector<vector<int>> G(n);
        for (auto &e : E) {
            int u = e[0], v = e[1];
            G[u].push_back(v);
            G[v].push_back(u);
        }
        vector<int> ans;
        for (auto &q : Q) {
            int start = q[0], end = q[1], node = q[2];
            function<int(int, int)> dfs = [&](int u, int prev) {
                int ans = -1;
                if (u == start || u == end) ans = u; // Forward the target node as potential LCA
                for (int v : G[u]) {
                    if (v == prev) continue;
                    int n = dfs(v, u);
                    if (n != -1) {
                        if (ans != -1) ans = u; // Forward the target node or LCA from children to the root
                        else ans = n; // If we've seen two target nodes, the current node is the LCA
                    }
                }
                return ans;
            };
            ans.push_back(dfs(node, -1));
        }
        return ans;
    }
};