每日一题:LeetCode:1719.重建一棵树的方案数

浏览次数 : 次 2022-02-16

博文字数统计 : 2.4k字 | 阅读所需时长 : 9分

× 文章目录

1. 2022-02-16：LeetCode：1719.重建一棵树的方案数

每日一题：LeetCode：1719.重建一棵树的方案数
- 时间：2022-02-16
- 力扣难度：Hard
- 个人难度：Hard+
- 数据结构：数组、树、图、邻接矩阵
- 算法：图论、拓扑排序

2022-02-16：LeetCode：1719.重建一棵树的方案数

1. 题目描述

题目：原题链接
- 给你一个数组 pairs ，其中 pairs[i] = [xi, yi] ，并且满足：
  - pairs 中没有重复元素
  - xi < yi
- 令 ways 为满足下面条件的有根树的方案数：
  - 树所包含的所有节点值都在 pairs 中。
  - 一个数对 [xi, yi] 出现在 pairs 中当且仅当 xi 是 yi 的祖先或者 yi 是 xi 的祖先。
  - 注意：构造出来的树不一定是二叉树。
  - 两棵树被视为不同的方案当存在至少一个节点在两棵树中有不同的父节点。
- 请你返回：
  - 如果 ways == 0 ，返回 0 。
  - 如果 ways == 1 ，返回 1 。
  - 如果 ways > 1 ，返回 2 。
- 一棵有根树指的是只有一个根节点的树，所有边都是从根往外的方向。
- 我们称从根到一个节点路径上的任意一个节点（除去节点本身）都是该节点的祖先。根节点没有祖先。
- 1 <= pairs.length <= 10^5
- 1 <= xi < yi <= 500
输入输出规范
- 输入：二维数组 pairs
- 输出：重建树的方案个数种类
输入输出示例
- 输入：pairs = [[1,2],[2,3],[1,3]]
- 输出：2

2. 方法一：邻接矩阵 & 分析节点的度 & 查找父节点

思路：父子节点的度之间存在一定的关系
- 本题虽然描述为重建一棵树，但实际考察的是图的相关内容
- 可以发现，对于输入的二维数组 pairs，每个数对 [xi, yi] 表示
  - xi 和 yi 两个节点在树中可以互为祖先节点
  - 等价于：xi 和 yi 两个顶点在图中是连通的，即是无向无权图
  - 本题中，顶点的度可以抽象为顶点的祖先集合的大小
  - 注意：由于数对中两个节点互为祖先，所以祖先集合实际上也包含了后代节点，即树上同一个路径的所有节点会在一个祖先集合中
- 因此，我们首先需要构造邻接矩阵，即对应前面提到的祖先集合，将数对中包含的顶点和边的信息解析出来
  - 由于不确定顶点的真实取值范围，可以使用Map来模拟邻接矩阵
  - 也可以根据题目给定的顶点小于500来设置二维矩阵、List集合来作为邻接矩阵
- 接下来，考虑一个数对 [A, B] 表示的 A、B 节点之间度的关系，设节点 A 的度为 d(A)
  - 首先，根节点的度一定等于节点总数 - 1，因为所有节点都是根节点的后代节点，有 d(root) = n - 1
  - 当重建的树中，如果节点 A 是 B 的祖先节点(父节点)，那么一定有d(A) >= d(B)，因为 B 的后代节点一定也是 A 的后代节点，同时，此时 B 节点的祖先集合一定是 A 的祖先集合的子集，如果这两个条件不满足，说明无法重建树
  - 当重建的树有多种方案时，就说明此时会有度相等的节点，且这些度相同的节点是在同一条路径上，即它们的祖先集合相同，可称为等效节点，可以替换顺序组成不同的方案
- 总结一下，先构造邻接矩阵，得到各个节点的祖先集合，然后分析根节点是否满足、任意一个节点是否具有父节点(度更大且祖先集合被包含)、是否存在等效节点

题解

public int checkWays(int[][] pairs) {
    if (pairs == null || pairs.length == 0) return -1;
    Map<Integer, Set<Integer>> map = new HashMap<>();
    // 各个节点的祖先子集
    for (int[] pair : pairs) {
        map.putIfAbsent(pair[0], new HashSet<>());
        map.get(pair[0]).add(pair[1]);
        map.putIfAbsent(pair[1], new HashSet<>());
        map.get(pair[1]).add(pair[0]);
    }
    int n = map.size();
    Set<Map.Entry<Integer, Set<Integer>>> entries = map.entrySet();
    // 根节点必须有 n - 1 个子节点
    int root = -1;
    for (Map.Entry<Integer, Set<Integer>> entry : entries) {
        int cur = entry.getKey();
        Set<Integer> nodes = entry.getValue();
        if(nodes.size() == n - 1) root = cur;
    }
    if(root == -1) return 0;
    int type = 1;
    // 其他节点：父子判断
    for (Map.Entry<Integer, Set<Integer>> entry : entries) {
        int cur = entry.getKey();
        if(cur == root) continue;
        Set<Integer> nodes = entry.getValue();
        int curSize = nodes.size();
        int parent = -1, parentSize = Integer.MAX_VALUE;
        // 查找当前节点的父节点，查找不到表示无法构成树
        for (int node : nodes) {
            int nodeSize = map.get(node).size();
            if(nodeSize >= curSize && nodeSize < parentSize) {
                parent = node;
                parentSize = nodeSize;
            }
        }
        if (parent == -1) return 0;
        // 父节点的子祖先子集一定包含子节点的祖先子集，否则无法构成树
        for (int node : nodes) {
            if(node == parent) continue;
            if(!map.get(parent).contains(node)) return 0;
        }
        // 判断是否存在多种重建方法，条件是两个父子节点的祖先子集相等
        if(parentSize == curSize) type = 2;
    }
    return type;
}

复杂度分析：m 是 pairs 数组的大小，n 是节点的个数
- 时间复杂度：$O(m+n^2)$，构建邻接矩阵是$O(m)$，分析度和查找父节点是$O(n^2)$
- 空间复杂度：$O(m)$，邻接矩阵的花销

3. 方法二：邻接矩阵 & 排序 & 自顶向下分析

思路
- 先回顾下方法一的邻接矩阵，使用Map的原因是不知道顶点的具体个数、以及顶点标号是否连续等
  - 但实际上只要直到最大的数据规模(本题是500)，就可以通过预先设置大小确定的数组来构造邻接矩阵，方法二使用List<List<Integer>>来模拟邻接矩阵
  - 当然也可以先对顶点计数，在设置邻接矩阵，但这会多进行几次遍历，没有必要
- 首先，还是构建邻接矩阵，同时利用一个Set存储所有顶点，后面用来排序
- 同时，还维护两个数组 count 和 parent，分别用来记录顶点的度、当前节点的父节点(可初始化为根节点)
- 然后，将 Set 转换为 List 并按照度的大小降序排序，这么做原因是重建的树中，度越大的节点离根越近，排序后我们可以自顶向下的来重建树，更新父节点
- 同样的，先分析根节点的度是否合法，即等于 n - 1
- 其次，遍历降序的节点数组，对于当前节点，遍历其邻接矩阵中的其他节点，即祖先集合中的节点
  - 如果存在度相同的节点，就可能存在多种方案(还需要判断是否合法)，不妨先将结果赋值为 2
  - 如果当前节点和祖先集合里面的节点的父节点不同，就对应方法一中后代节点的祖先集合不是当前节点的子集的情况，表明无法重建树，直接返回 0
  - 如果两者父节点相同，那么将遍历到的这个后代节点的父节点更新为外层的当前节点
- 遍历完所有节点后，返回结果即可，结果的初始值为 1
- 值得注意的是，在遍历当前节点的时候
  - 由于还要在内层遍历其后代节点，所以可能会多次访问同一个节点
  - 多次访问不但降低效率，同时由于可能在访问其他节点的时候更新了该节点的父节点，导致重新访问时误判为父节点不一致而出错
  - 因此，需要维护一个布尔数组，表示节点是否在外层循环时被访问过，只有没访问过的才会在内层访问

题解

int N = 505;
int[] count = new int[N]; // 祖先集合个数
int[] parent = new int[N]; // 父节点
boolean[] visited = new boolean[N];

public int checkWays(int[][] pairs) {
    if (pairs == null || pairs.length == 0) return -1;
    // 记录节点个数
    Set<Integer> set = new HashSet<>();
    // 邻接矩阵 : 祖先子集
    List<List<Integer>> edges = new ArrayList<>(N);
    for (int i = 0; i < N; i++) {
        edges.add(new ArrayList<>());
    }
    // 各个节点的祖先子集
    for (int[] pair : pairs) {
        int x = pair[0], y = pair[1];
        count[x]++;
        count[y]++;
        set.add(x);
        set.add(y);
        edges.get(x).add(y);
        edges.get(y).add(x);
        parent[x] = -1;
        parent[y] = -1;
    }

    int n = set.size(), m = pairs.length;
    if(m < n - 1) return 0;
    if(m == n*(n - 1)/2) return 2;
    List<Integer> nodes = new ArrayList<>(set);
    nodes.sort((o1, o2) -> count[o2] - count[o1]);
    // 根节点判断
    if (count[nodes.get(0)] != n - 1) return 0;
    int type = 1;
    // 其他节点
    for (int i = 0; i < n; i++) {
        int curNode = nodes.get(i); // 当前节点
        List<Integer> adjNodes = edges.get(curNode);
        for (int adjNode : adjNodes) {
            // 两个父子节点的祖先子集个数相等
            if(count[curNode] == count[adjNode]) type = 2;
            if(!visited[adjNode]){
                // 父节点不同时，无法构造树
                if(parent[curNode] != parent[adjNode]) return 0;
                parent[adjNode] = curNode;
            }
        }
        visited[curNode] = true;
    }
    return type;
}

复杂度分析：m 是 pairs 数组的大小，n 是节点的个数
- 时间复杂度：$O(m+n^2)$，构建邻接矩阵是$O(m)$，分析度和查找父节点是$O(n^2)$
- 空间复杂度：$O(m)$，邻接矩阵的花销

本文作者： Chthollists
发布时间： 2022-02-16 23:21:50
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1719.重建一棵树的方案数
本文链接： https://chthollists.github.io/post/e539051c.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！