Сложность: 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, чтобы получить фактическое количество.
😎 Решение:
public class Solution {
public int CountPairs(TreeNode root, int distance) {
var graph = new Dictionary<TreeNode, List<TreeNode>>();
var leafNodes = new HashSet<TreeNode>();
TraverseTree(root, null, graph, leafNodes);
int ans = 0;
foreach (var leaf in leafNodes) {
var bfsQueue = new Queue<TreeNode>();
var seen = new HashSet<TreeNode>();
bfsQueue.Enqueue(leaf);
seen.Add(leaf);
for (int i = 0; i <= distance; i++) {
int size = bfsQueue.Count;
for (int j = 0; j < size; j++) {
var currNode = bfsQueue.Dequeue();
if (leafNodes.Contains(currNode) && currNode != leaf) {
ans++;
}
if (graph.ContainsKey(currNode)) {
foreach (var neighbor in graph[currNode]) {
if (!seen.Contains(neighbor)) {
bfsQueue.Enqueue(neighbor);
seen.Add(neighbor);
}
}
}
}
}
}
return ans / 2;
}
private void TraverseTree(TreeNode currNode, TreeNode prevNode,
Dictionary<TreeNode, List<TreeNode>> graph, HashSet<TreeNode> leafNodes) {
if (currNode == null) {
return;
}
if (currNode.left == null && currNode.right == null) {
leafNodes.Add(currNode);
}
if (prevNode != null) {
if (!graph.ContainsKey(prevNode)) {
graph[prevNode] = new List<TreeNode>();
}
graph[prevNode].Add(currNode);
if (!graph.ContainsKey(currNode)) {
graph[currNode] = new List<TreeNode>();
}
graph[currNode].Add(prevNode);
}
TraverseTree(currNode.left, currNode, graph, leafNodes);
TraverseTree(currNode.right, currNode, graph, leafNodes);
}
}Ставь 👍 и забирай 📚 Базу знаний