---
# System prepended metadata

title: 2359. Find Closest Node to Given Two Nodes
tags: [Leetcode, DFS]

---

# 2359. Find Closest Node to Given Two Nodes
###### tags: `Leetcode` `DFS`
Link: https://leetcode.com/problems/find-closest-node-to-given-two-nodes/description/
## 思路
思路参考[这里](https://leetcode.com/problems/find-closest-node-to-given-two-nodes/solutions/2357694/two-dfs/)
对两个点分别做dfs
找到这两点分别和每个点的距离
然后找到最大距离最小的那个
注意:由于每个点最多只有一个outgoing edge 其实这个图就像是一个linkedlist, current node和next node直接是straightforward的 不需要像之前一样做bfs/dfs
## Code
```java=
class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[] dist1 = new int[n];
        int[] dist2 = new int[n];
        Arrays.fill(dist1, -1);
        Arrays.fill(dist2, -1);
        dfs(node1, edges, dist1);
        dfs(node2, edges, dist2);
        int minDist = Integer.MAX_VALUE;
        int ans = -1;
        for(int i=0; i<n; i++){
            if(Math.min(dist1[i], dist2[i])>=0 && Math.max(dist1[i], dist2[i])<minDist){
                minDist = Math.max(dist1[i], dist2[i]);
                ans = i;
            }
        }
        return ans;
    }
    public void dfs(int node, int[] edges, int[] memo){
        int dist = 0;
        while(node!=-1 && memo[node]==-1){
            memo[node] = dist++;
            node = edges[node];
        }
    }
}
```