[LeetCode] 每日一题 2359. 找到离给定两个节点最近的节点（DFS）

题目描述

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

题目链接

https://leetcode.cn/problems/find-closest-node-to-given-two-nodes

示例输入

示例 1

输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。

示例 2

输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。

提示

• n == edges.length

• 2 <= n <= 10^5

• -1 <= edges[i] < n

• edges[i] != i

• 0 <= node1, node2 < n

解题思路

这几天的题目都有点“图论串烧”的感觉，比如前两天遇到树结构问题时，如果原始存储结构不满足需求，我就用 DFS 先手动遍历一遍，把想要的信息构造出来，再开始求解。

这道题同样如此。题目给出的是一个每个节点最多只有一条出边的有向图，也就是说每个节点最多向外走一步，整体可以看作一个由链、树、环组成的图结构。

我们需要找一个“中间节点”，这个节点能同时从 node1 和 node2 到达，并且我们要让这两个点到它的最远距离尽量小（取较大值的最小化）。这是典型的“从两个起点分别向外扩展”，然后比较交集的做法。

所以我先写了一个 getDistances() 方法，类似 DFS 的遍历方式，但由于图可能有环，我用一个数组标记是否访问过，每次记录每个点到起点的距离。

接着遍历每个节点，如果该点能同时从两个起点到达，就计算两者到它的距离的较大值，然后维护一个最小值和对应的节点编号即可。

代码实现

class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[] distances1 = getDistances(edges, node1);
        int[] distances2 = getDistances(edges, node2);
        int ans = -1;
        int distance = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int dis1 = distances1[i];
            int dis2 = distances2[i];
            if (dis1 != -1 && dis2 != -1) {
                int max = Math.max(dis1, dis2);
                if (max < distance) {
                    distance = max;
                    ans = i;
                }
            }
        }
        return ans;
    }

    private int[] getDistances(int[] edges, int index) {
        int n = edges.length;
        int[] distances = new int[n];
        Arrays.fill(distances, -1);
        int distance = 0;
        while (index != -1 && distances[index] == -1) {
            distances[index] = distance;
            distance++;
            index = edges[index];
        }
        return distances;
    }
}

复杂度分析

• 时间复杂度：

  • O(n)，我们最多遍历每个节点一次构造距离，最终再线性扫描一次找答案

• 空间复杂度：

  • O(n)，用于记录每个起点到其他节点的距离

总结

本题是一道典型的“有向图路径遍历 + 双起点合流”问题。在题目结构简单但带环的前提下，用 DFS 变种构造距离数组是一种常见且高效的手段。这种“先构造状态，再一轮扫一遍找答案”的模式在图和树题中非常常见，建议作为通用解法模板记住～🫠

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。