标签： dfs

目标

给你一棵无根带权树，树中总共有 n 个节点，分别表示 n 个服务器，服务器从 0 到 n - 1 编号。同时给你一个数组 edges ，其中 edges[i] = [ai, bi, weighti] 表示节点 ai 和 bi 之间有一条双向边，边的权值为 weighti 。再给你一个整数 signalSpeed 。

如果两个服务器 a ，b 和 c 满足以下条件，那么我们称服务器 a 和 b 是通过服务器 c 可连接的 ：

• a < b ，a != c 且 b != c 。
• 从 c 到 a 的距离是可以被 signalSpeed 整除的。
• 从 c 到 b 的距离是可以被 signalSpeed 整除的。
• 从 c 到 b 的路径与从 c 到 a 的路径没有任何公共边。

请你返回一个长度为 n 的整数数组 count ，其中 count[i] 表示通过服务器 i 可连接 的服务器对的 数目 。

说明：

• 2 <= n <= 1000
• edges.length == n - 1
• edges[i].length == 3
• 0 <= ai, bi < n
• edges[i] = [ai, bi, weighti]
• 1 <= weighti <= 10^6
• 1 <= signalSpeed <= 10^6
• 输入保证 edges 构成一棵合法的树。

思路

有一颗无根带权树，所有到服务器 c 的路径，如果路径长度能够被 signalSpeed 整除，并且路径没有重合，则这些服务器可以通过 c 连接。即 c 的每个分支上满足条件的节点可以与其它分支满足条件的节点连接。

遍历每一个节点，以其为根，使用dfs分别计算各分支满足条件的节点，然后计算服务器对。

假设根节点R有4个分支，每个分支上满足条件的节点个数为 a、b、c、d，我们可以使用下面两个方法计算服务器对：

for：
    a：ab + ac + ad
    b：bc + bd
    c：cd

或者

for
    a：0 * a
    b：a * b
    c：(a+b) * c
    d：(a+b+c) * d

第二种方法计算的其实是第一种方法斜线上的和
    a：ab + ac + ad
          /    /
    b：bc + bd
          /
    c：cd

最快的解法应该是换根dp，但是换根后节点数如何变化，处理起来比较复杂，考虑的情况也更多，容易出错。

代码

/**
 * @date 2024-06-04 8:41
 */
public class CountPairsOfConnectableServers3067 {

    private List<int[]>[] g;
    private int speed;

    public int[] countPairsOfConnectableServers_v1(int[][] edges, int signalSpeed) {
        int n = edges.length;
        g = new List[n + 1];
        speed = signalSpeed;
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            g[edges[i][0]].add(new int[]{edges[i][1], edges[i][2]});
            g[edges[i][1]].add(new int[]{edges[i][0], edges[i][2]});
        }
        for (int i = 0; i <= n; i++) {
            int pre = 0;
            if (g[i].size() == 1) {
                continue;
            }
            for (int j = 0; j < g[i].size(); j++) {
                int cnt = dfs(g[i].get(j)[0], i, g[i].get(j)[1]);
                res[i] += pre * cnt;
                pre += cnt;
            }
        }
        return res;
    }

    public int dfs(int root, int parent, int path) {
        int cnt = path % speed == 0 ? 1 : 0;
        if (g[root].size() == 1 && parent != -1) {
            return cnt;
        }
        for (int[] child : g[root]) {
            if (child[0] == parent) {
                continue;
            }
            cnt += dfs(child[0], root, path + child[1]);
        }
        return cnt;
    }

}

性能

目标

给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。

每分钟，如果节点满足以下全部条件，就会被感染：

• 节点此前还没有感染。
• 节点与一个已感染节点相邻。

返回感染整棵树需要的分钟数。

示例 1：

输入：root = [1,5,3,null,4,10,6,9,2], start = 3
输出：4
解释：节点按以下过程被感染：
- 第 0 分钟：节点 3
- 第 1 分钟：节点 1、10、6
- 第 2 分钟：节点5
- 第 3 分钟：节点 4
- 第 4 分钟：节点 9 和 2
感染整棵树需要 4 分钟，所以返回 4 。

示例 2：

输入：root = [1], start = 1
输出：0
解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。

说明：

• 树中节点的数目在范围 [1, 10^5] 内
• 1 <= Node.val <= 10^5
• 每个节点的值 互不相同
• 树中必定存在值为 start 的节点

思路

从树中任意节点开始，每过一分钟感染会向周围扩散，问感染整棵树需要多久。

首先我们要找到感染开始的节点。从这个节点出发，向左右子树点以及父节点扩散。可以将树转换为以感染节点为起点的有向无环连通图，这样问题被转换为求起点到图中任意节点的最长路径。

如果不想建图可以考虑扩散的具体路径，刚开始很难把各种情况都考虑到。我们需要计算以开始节点为根的子树高度 h(start)，并依次比较开始节点到祖先节点路径长度加上祖先另一子树高度的最大值，即max(d(start) - d(ancestor) + h(anotherAncestorSubtree))，再取二者的最大值即可。特别需要注意的是，不能使用子树高度之差来计算祖先与开始节点的路径长度。例如，E是开始节点，E到B的路径长度为d(E) - d(B) = 2 - 1 = 1，而如果使用子树高度相减的话就得到了h(B) - h(E) = 3 - 0 = 3。

      A
    /   \
   B     C
  / \
 D   E
 |
 F
 |
 G

在具体实现的时候如何判断祖先节点的哪个子树包含开始节点困扰了我半天。刚开始我选择了一个标志位，分别在左右子树递归结束的时候检测该标志，发现找到之后立即重置该标志，这样父节点就知道了是左子树还是右子树包含开始节点。但问题是再向上返回的时候就无法判断了。

可以考虑返回二维数组，也有网友的题解使用返回值的符号来标识是否找到开始节点。

代码

/**
 * @date 2024-04-24 8:56
 */
public class AmountOfTime2385 {
    int startToParentToLeaf = 0;
    int startToLeaf = 0;
    int cnt = 0;

    public int amountOfTime(TreeNode root, int start) {
        dfs(root, start);
        return Math.max(startToLeaf, startToParentToLeaf);
    }

    /**
     * 返回子树深度
     */
    public int[] dfs(TreeNode root, int start) {
        if (root == null) {
            return new int[]{0, 0};
        }

        int[] l = dfs(root.left, start);
        int[] r = dfs(root.right, start);
        boolean lfind = l[1] == 1;
        boolean rfind = r[1] == 1;
        int max = Math.max(r[0], l[0]);

        if (lfind || rfind) {
            startToParentToLeaf = Math.max(startToParentToLeaf, l[0] + r[0]);
            // 这里的返回值不是max，而是祖先节点到开始节点的路径长度
            return new int[]{(lfind ? l[0] : r[0]) + 1, 1};
        }
        if (root.val == start) {
            startToLeaf = max;
            // 这里直接返回1，不加max
            // 视为将开始节点的左右子树删掉，后面回溯时直接相加左右子树高度即可
            return new int[]{1, 1};
        }
        return new int[]{max + 1, 0};
    }

    /**
     * 返回深度
     */
    public int[] dfs_v1(TreeNode root, int start, int depth) {
        if (root == null) {
            return new int[]{depth - 1, 0};
        }

        int[] l = dfs_v1(root.left, start, depth + 1);
        int[] r = dfs_v1(root.right, start, depth + 1);
        boolean lfind = l[1] == 1;
        boolean rfind = r[1] == 1;
        int max = Math.max(r[0], l[0]);
        if (lfind) {
            cnt++;
            startToParentToLeaf = Math.max(r[0] - depth + cnt, startToParentToLeaf);
        }
        if (rfind) {
            cnt++;
            startToParentToLeaf = Math.max(l[0] - depth + cnt, startToParentToLeaf);
        }
        if (root.val == start) {
            startToLeaf = max - depth;
            return new int[]{max, 1};
        }
        return new int[]{max, l[1] + r[1]};
    }
}

性能

目标

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

说明：

• 树中的节点数在 2 到 5000 之间。
• 0 <= Node.val <= 10^5

思路

这道题还是挺直观的，求节点与其祖先之间的最大差值。直接深度优先遍历，记录路径上的最大与最小值，同时计算最大差值即可。

代码

/**
 * @date 2024-04-05 0:13
 */
public class MaxAncestorDiff1026 {

    int res = 0;

    public int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);
        return res;
    }

    public void dfs(TreeNode node, int max, int min) {
        if (node == null) {
            return;
        }
        max = Math.max(node.val, max);
        min = Math.min(node.val, min);
        res = Math.max(res, max - min);
        dfs(node.left, max, min);
        dfs(node.right, max, min);
    }
}

性能

目标

现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。

给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示 受限 节点。

在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目。

注意，节点 0 不 会标记为受限节点。

思路

自然的想法是构建图，将受限节点从中删除，然后深度优先遍历，同时记录节点个数。这里构建的图主要是为了获取其连通节点进行dfs，HashSet不太适合。因为数据可能并不是连续存储的，要先计算元素的Hash值，然后从桶中取出链表或者红黑树，才能找到元素。在本例中，性能会下降一倍。

代码

/**
 * @date 2024-03-02 15:39
 */
public class ReachableNodes {
    public int res = 1;
    boolean[] isRestricted;

    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        List<Integer>[] g = new ArrayList[edges.length + 1];
        isRestricted = new boolean[edges.length + 1];
        for (int i : restricted) {
            isRestricted[i] = true;
        }
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            if (isRestricted[edge[0]] || isRestricted[edge[1]]) {
                continue;
            }
            g[edge[0]].add(edge[1]);
            g[edge[1]].add(edge[0]);
        }
        dfs(0, -1, g);
        return res;
    }

    public void dfs(int root, int parent, List<Integer>[] g) {
        for (Integer n : g[root]) {
            if (n == parent) {
                continue;
            }
            res++;
            dfs(n, root, g);
        }
    }
}

性能

看了官网的答案还可以使用并查集，耗时只要10ms，有时间可以看看。