Leetcode 2359. 找到离给定两个节点最近的节点

原题链接：Leetcode 2359. 找到离给定两个节点最近的节点


DFS:

class Solution {
public:vector<int> dis1;vector<int> dis2;vector<int> visit;void dfs(vector<int>& edges,int now,int d,int flag){if(flag==1) dis1[now]=d;else dis2[now]=d;visit[now]=1;if(edges[now]!=-1 && !visit[edges[now]]) dfs(edges,edges[now],d+1,flag);}int closestMeetingNode(vector<int>& edges, int node1, int node2) {int n=edges.size();dis1.resize(n,-1);dis2.resize(n,-1);visit.resize(n);dfs(edges,node1,0,1);for(int i=0;i<n;i++) visit[i]=0;dfs(edges,node2,0,2);int dis=INT_MAX,node=n-1;for(int i=0;i<n;i++){if(dis1[i]!=-1 && dis2[i]!=-1){int tmp=max(dis1[i],dis2[i]);if(tmp<dis){dis=tmp;node=i;}}}return dis==INT_MAX? -1:node;}
};

循环：

class Solution {
public:vector<int> dis1;vector<int> dis2;void dfs(vector<int>& edges,int now,int flag){if(flag==1) dis1[now]=0;else dis2[now]=0;int d=0;while(edges[now]!=-1){now=edges[now];d+=1;if(flag==1 && dis1[now]==-1) dis1[now]=d;else if(flag==2 && dis2[now]==-1) dis2[now]=d;else break;}}int closestMeetingNode(vector<int>& edges, int node1, int node2) {int n=edges.size();dis1.resize(n,-1);dis2.resize(n,-1);dfs(edges,node1,1);dfs(edges,node2,2);int dis=INT_MAX,node=n-1;for(int i=0;i<n;i++){if(dis1[i]!=-1 && dis2[i]!=-1){int tmp=max(dis1[i],dis2[i]);if(tmp<dis){dis=tmp;node=i;}}}return dis==INT_MAX? -1:node;}
};