Сложность: medium
Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance.
Верните количество хороших пар листовых узлов в дереве.
Пример:
Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.
👨💻 Алгоритм:
1⃣Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла.
2⃣Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS.
3⃣Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.
😎 Решение:
class Solution {
public int countPairs(TreeNode root, int distance) {
Map<TreeNode, List<TreeNode>> graph = new HashMap<>();
Set<TreeNode> leafNodes = new HashSet<>();
traverseTree(root, null, graph, leafNodes);
int ans = 0;
for (TreeNode leaf : leafNodes) {
Queue<TreeNode> bfsQueue = new LinkedList<>();
Set<TreeNode> seen = new HashSet<>();
bfsQueue.add(leaf);
seen.add(leaf);
for (int i = 0; i <= distance; i++) {
int size = bfsQueue.size();
for (int j = 0; j < size; j++) {
TreeNode currNode = bfsQueue.remove();
if (leafNodes.contains(currNode) && currNode != leaf) {
ans++;
}
if (graph.containsKey(currNode)) {
for (TreeNode neighbor : graph.get(currNode)) {
if (!seen.contains(neighbor)) {
bfsQueue.add(neighbor);
seen.add(neighbor);
}
}
}
}
}
}
return ans / 2;
}
private void traverseTree(
TreeNode currNode,
TreeNode prevNode,
Map<TreeNode, List<TreeNode>> graph,
Set<TreeNode> leafNodes
) {
if (currNode == null) {
return;
}
if (currNode.left == null && currNode.right == null) {
leafNodes.add(currNode);
}
if (prevNode != null) {
graph.computeIfAbsent(prevNode, k -> new ArrayList<TreeNode>());
graph.get(prevNode).add(currNode);
graph.computeIfAbsent(currNode, k -> new ArrayList<TreeNode>());
graph.get(currNode).add(prevNode);
}
traverseTree(currNode.left, currNode, graph, leafNodes);
traverseTree(currNode.right, currNode, graph, leafNodes);
}
}Ставь 👍 и забирай 📚 Базу знаний