找到离给定两个节点最近的节点 - C++力扣2359题

题目链接：https://leetcode.com/problems/find-closest-node-to-given-two-nodes/description/

解题思路

这题目其实算是容易到中等难度之间，基本上就先走一趟整个图然后找到答案就行，就是题目有点绕："请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。"

反正就是 dfs 走一遍记录下来走过哪以及对应的距离，这个图也不到很过分，没有带路径距离，所以每走一次就 +1 就行。然后只需要读懂那个 较大值最小化 基本上就能知道这题该这么造了。

完整代码：

class Solution {
public:

    void dfs(int now, vector<int> &edges, vector<int> &dist, vector<bool> &visited) {
        if(now == -1) return ;
        if(visited[now] == true) return ;

        visited[now] = true;
        if(edges[now] != -1 && visited[edges[now]] == false) dist[edges[now]] = dist[now] + 1;

        return dfs(edges[now], edges, dist, visited);
    }

    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        vector<int> dist1(edges.size(), 0), dist2(edges.size(), 0);
        vector<bool> visited1(edges.size(), false), visited2(edges.size(), false);

        int maxDist = INT_MAX;
        int ans = -1;

        dfs(node1, edges, dist1, visited1);
        dfs(node2, edges, dist2, visited2);

        for(int i = 0; i < edges.size(); i++) {
            if(visited1[i] == true && visited2[i] == true && maxDist > max(dist1[i], dist2[i])) {
                maxDist = max(dist1[i], dist2[i]);
                ans = i;
            }
        }

        return ans;
    }
};