1530. Number of Good Leaf Nodes Pairs
LeetCode
medium
оригинал: C#
#csharp
#graph
#hash-table
#leetcode
#medium
#queue
#recursion
#tree
#two-pointers
Вам дан корень бинарного дерева и целое число 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.
C# решение
сопоставлено/оригинал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);
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int CountPairs(TreeNode root, int distance) {
var graph = new unordered_map<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.push_back(leaf);
for (int i = 0; i <= distance; i++) {
int size = bfsQueue.size();
for (int j = 0; j < size; j++) {
var currNode = bfsQueue.Dequeue();
if (leafNodes.Contains(currNode) && currNode != leaf) {
ans++;
}
if (graph.count(currNode)) {
foreach (var neighbor in graph[currNode]) {
if (!seen.Contains(neighbor)) {
bfsQueue.Enqueue(neighbor);
seen.push_back(neighbor);
}
}
}
}
}
}
return ans / 2;
}
private void TraverseTree(TreeNode currNode, TreeNode prevNode,
unordered_map<TreeNode, List<TreeNode>> graph, HashSet<TreeNode> leafNodes) {
if (currNode == null) {
return;
}
if (currNode.left == null && currNode.right == null) {
leafNodes.push_back(currNode);
}
if (prevNode != null) {
if (!graph.count(prevNode)) {
graph[prevNode] = new List<TreeNode>();
}
graph[prevNode].push_back(currNode);
if (!graph.count(currNode)) {
graph[currNode] = new List<TreeNode>();
}
graph[currNode].push_back(prevNode);
}
TraverseTree(currNode.left, currNode, graph, leafNodes);
TraverseTree(currNode.right, currNode, graph, leafNodes);
}
}Java решение
сопоставлено/оригинал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);
}
}Python решение
сопоставлено/оригиналclass Solution:
def countPairs(self, root: TreeNode, distance: int) -> int:
graph = defaultdict(list)
leafNodes = set()
self.traverseTree(root, None, graph, leafNodes)
ans = 0
for leaf in leafNodes:
bfsQueue = deque([leaf])
seen = set([leaf])
for i in range(distance + 1):
size = len(bfsQueue)
for _ in range(size):
currNode = bfsQueue.popleft()
if currNode in leafNodes and currNode != leaf:
ans += 1
for neighbor in graph[currNode]:
if neighbor not in seen:
bfsQueue.append(neighbor)
seen.add(neighbor)
return ans // 2
def traverseTree(self, currNode, prevNode, graph, leafNodes):
if not currNode:
return
if not currNode.left and not currNode.right:
leafNodes.add(currNode)
if prevNode:
graph[prevNode].append(currNode)
graph[currNode].append(prevNode)
self.traverseTree(currNode.left, currNode, graph, leafNodes)
self.traverseTree(currNode.right, currNode, graph, leafNodes)Go решение
сопоставлено/оригиналtype TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func countPairs(root *TreeNode, distance int) int {
graph := make(map[*TreeNode][]*TreeNode)
leafNodes := make(map[*TreeNode]bool)
traverseTree(root, nil, graph, leafNodes)
ans := 0
for leaf := range leafNodes {
bfsQueue := []*TreeNode{leaf}
seen := make(map[*TreeNode]bool)
seen[leaf] = true
for i := 0; i <= distance; i++ {
size := len(bfsQueue)
for j := 0; j < size; j++ {
currNode := bfsQueue[0]
bfsQueue = bfsQueue[1:]
if leafNodes[currNode] && currNode != leaf {
ans++
}
for _, neighbor := range graph[currNode] {
if !seen[neighbor] {
bfsQueue = append(bfsQueue, neighbor)
seen[neighbor] = true
}
}
}
}
}
return ans / 2
}
func traverseTree(currNode, prevNode *TreeNode, graph map[*TreeNode][]*TreeNode, leafNodes map[*TreeNode]bool) {
if currNode == nil {
return
}
if currNode.Left == nil && currNode.Right == nil {
leafNodes[currNode] = true
}
if prevNode != nil {
graph[prevNode] = append(graph[prevNode], currNode)
graph[currNode] = append(graph[currNode], prevNode)
}
traverseTree(currNode.Left, currNode, graph, leafNodes)
traverseTree(currNode.Right, currNode, graph, leafNodes)
}Algorithm
Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла.
Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS.
Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.