LeetCode 题解 - 3203. Find Minimum Diameter After Merging Two Trees

题目链接：3203. Find Minimum Diameter After Merging Two Trees

There exist two undirected trees with n and m nodes, numbered from 0 to n - 1 and from 0 to m - 1, respectively. You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the first tree and edges2[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the second tree.

You must connect one node from the first tree with another node from the second tree with an edge.

Return the minimum possible diameter of the resulting tree.

The diameter of a tree is the length of the longest path between any two nodes in the tree.

题目模版：

class Solution {
 public:
  int minimumDiameterAfterMerge(const std::vector<std::vector<int>>& edges1,
                                const std::vector<std::vector<int>>& edges2) {}
}

这是一道很考验对树（Tree）数据结构直觉的题目。

首先，要在把两棵树 $Tree_1$ 和 $Tree_2$ 接到一起之后保持 $Tree_{1+2}$ 的直径 $Diameter(Tree_{1+2})$ 最小，应该怎么接？从直觉上考虑，我们应该找到 $Tree_1$ 和 $Tree_2$ 的“中心结点”^1 $Node_1$ 和 $Node_2$，然后把它们接到一起。一棵树的中心结点可能有两个。对于本问题，我们取其中任意一个作为中心结点。

在这里我们定义树的半径 $Radius(Tree)$ ：树 $Tree$ 的中心结点到任意其他结点的最大距离。明显地，

• 如果中心结点只有一个，那么有 $Radius(Tree) = Diameter(Tree) / 2$。
• 如果中心结点有两个，那么有 $Radius(Tree) = Ceil(Diameter(Tree) / 2)$。

因此 $Radius(Tree) = Ceil(Diameter(Tree) / 2)$。

那么，接到一起之后，最小的直径可能是什么？分三种情况：

1. 若计算 $Tree_{1+2}$ 的直径不需要经过 $Tree_1$ 的结点，那么最小直径就是 $Diameter(Tree_1)$。
2. 同理，若计算 $Tree_{1+2}$ 的直径不需要经过 $Tree_2$ 的结点，那么最小直径就是 $Diameter(Tree_2)$。
3. 若计算 $Tree_{1+2}$ 的直径需要同时经过 $Tree_1$ 和 $Tree_2$ 的结点，那么最小直径 $Radius(Tree_1) + Radius(Tree_2) + 1$。

总之， $$Diameter(Tree_{1+2}) = Max(Diameter(Tree_1), Diameter(Tree_2), Radius(Tree_1) + Radius(Tree_2) + 1)$$ 那么我们如何

写成代码：

class Solution {
 public:
  int minimumDiameterAfterMerge(const std::vector<std::vector<int>>& edges1,
                                const std::vector<std::vector<int>>& edges2) {
    const int tree1Diameter = ...;
    const int tree2Diameter = ...;

    const int connectedDiameter =
        static_cast<int>(std::ceil(static_cast<double>(tree1Diameter) / 2) +
                         std::ceil(static_cast<double>(tree2Diameter) / 2)) +
        1;

    return std::max({tree1Diameter, tree2Diameter, connectedDiameter});
  }
}

此时问题只剩下如何得到 $Diameter(Tree)$。

计算 $Diameter(Tree)$ 时，经过路径两端的结点一定都是叶子结点。因此，利用拓扑排序（Topological Sorting），在每轮删除所有叶子结点时给直径 $+2$，直到只剩下一个或两个结点。如果剩下两个结点，再给直径 $+1$ 即可。要使用拓扑排序，我们需要先将题目中给的边数组转换成邻接表：

std::unordered_map<int, std::unordered_set<int>>
  getNodeToNeighborsFromEdges(const std::vector<std::vector<int>>& edges) {
  const int kNodeNumber = static_cast<int>(edges.size()) + 1;
  std::unordered_map<int, std::unordered_set<int>> nodeToNeighbors;
  for (int i = 0; i < kNodeNumber; i++) {
    nodeToNeighbors.insert({i, std::unordered_set<int>()});
  }

  for (const auto& edge : edges) {
    nodeToNeighbors[edge[0]].insert(edge[1]);
    nodeToNeighbors[edge[1]].insert(edge[0]);
  }

  return nodeToNeighbors;
}

然后实现拓扑排序计算直径：

int getDiameter(
    const std::unordered_map<int, std::unordered_set<int>>& nodeToNeighbors) {
  const int kNodeNumber = static_cast<int>(nodeToNeighbors.size());

  int diameter = 0;
  int remainingNodes = kNodeNumber;
  std::vector<int> nodeToDegrees(kNodeNumber);
  std::queue<int> leavesNodeQueue;

  for (const auto& nodeToNeighbor : nodeToNeighbors) {
    nodeToDegrees[nodeToNeighbor.first] =
        static_cast<int>(nodeToNeighbor.second.size());
  }

  for (int i = 0; i < kNodeNumber; i++) {
    if (nodeToDegrees[i] == 1) {
      leavesNodeQueue.push(i);
    }
  }

  while (remainingNodes > 2) {
    // Every time a layer of leaf nodes is removed, the tree loses 2 diameter.
    diameter += 2;
    std::vector<int> nodesToRemove;
    while (!leavesNodeQueue.empty()) {
      const int leafNode = leavesNodeQueue.front();
      leavesNodeQueue.pop();
      nodesToRemove.push_back(leafNode);
    }

    for (const int nodeToRemove : nodesToRemove) {
      nodeToDegrees[nodeToRemove]--;
      remainingNodes--;

      for (const int neighborNode : nodeToNeighbors.at(nodeToRemove)) {
        nodeToDegrees[neighborNode]--;

        // New leaf nodes must be produced after current leaf nodes are
        // removed.
        if (nodeToDegrees[neighborNode] == 1) {
          leavesNodeQueue.push(neighborNode);
        }
      }
    }
  }

  if (remainingNodes == 2) {
    diameter++;
  }
  return diameter;
}

之后我们就可以完成题解了：

class Solution {
 public:
  int minimumDiameterAfterMerge(const std::vector<std::vector<int>>& edges1,
                                const std::vector<std::vector<int>>& edges2) {
    std::unordered_map<int, std::unordered_set<int>> tree1NodeToNeighbors =
        getNodeToNeighborsFromEdges(edges1);
    std::unordered_map<int, std::unordered_set<int>> tree2NodeToNeighbors =
        getNodeToNeighborsFromEdges(edges2);
    const int tree1Diameter = getDiameter(tree1NodeToNeighbors);
    const int tree2Diameter = getDiameter(tree2NodeToNeighbors);

    const int connectedDiameter =
        static_cast<int>(std::ceil(static_cast<double>(tree1Diameter) / 2) +
                         std::ceil(static_cast<double>(tree2Diameter) / 2)) +
        1;

    return std::max({tree1Diameter, tree2Diameter, connectedDiameter});
  }
}