Dado un árbol binario , un Node objetivo y un entero positivo K en él, la tarea es encontrar la suma de todos los Nodes dentro de la distancia K del Node objetivo (incluido el valor del Node objetivo en la suma).
Ejemplos:
Entrada: destino = 9, K = 1,
Árbol binario = 1
/ \
2 9
/ / \
4 5 7
/ \ / \
8 19 20 11
/ / \
30 40 50
Salida: 22
Explicación: Los Nodes dentro de la distancia 1 desde 9 son 9 + 5 + 7 + 1 = 22Entrada: objetivo = 40, K = 2,
Árbol binario = 1
/ \
2 9
/ / \
4 5 7
/ \ / \
8 19 20 11
/ / \
30 40 50
Salida: 113
Explicación: Los Nodes dentro de la distancia 2 desde 40 es
40 + 19 + 50 + 4 = 113
Enfoque: este problema se puede resolver utilizando hash y profundidad-primera-búsqueda en base a la siguiente idea:
Utilice una estructura de datos para almacenar el padre de cada Node. Ahora utilice esa estructura de datos para realizar un recorrido DFS desde el objetivo y calcule la suma de todos los Nodes dentro de una distancia K de ese Node.
Siga los pasos que se mencionan a continuación para implementar el enfoque:
- Cree una tabla hash (digamos par ) para almacenar el padre de cada Node.
- Realice un DFS y almacene el padre de cada Node.
- Ahora encuentra el objetivo en el árbol.
- Cree una tabla hash para marcar los Nodes visitados.
- Inicie un DFS desde el destino :
- Si la distancia no es K, suma el valor en la suma final.
- Si no se visita el Node, continúe el recorrido DFS para sus vecinos también (es decir, padre e hijo) con la ayuda de par y los enlaces de cada Node.
- Devuelve la suma de sus vecinos mientras se completa la recursión para el Node actual
- Devuelve la suma de todos los Nodes a una distancia K del objetivo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a tree node
struct Node {
int data;
Node* left;
Node* right;
Node(int val)
{
this->data = val;
this->left = 0;
this->right = 0;
}
};
// Function for marking the parent node
// for all the nodes using DFS
void dfs(Node* root,
unordered_map<Node*, Node*>& par)
{
if (root == 0)
return;
if (root->left != 0)
par[root->left] = root;
if (root->right != 0)
par[root->right] = root;
dfs(root->left, par);
dfs(root->right, par);
}
// Function calling for finding the sum
void dfs3(Node* root, int h, int& sum, int k,
unordered_map<Node*, int>& vis,
unordered_map<Node*, Node*>& par)
{
if (h == k + 1)
return;
if (root == 0)
return;
if (vis[root])
return;
sum += root->data;
vis[root] = 1;
dfs3(root->left, h + 1, sum, k, vis, par);
dfs3(root->right, h + 1, sum, k, vis, par);
dfs3(par[root], h + 1, sum, k, vis, par);
}
// Function for finding
// the target node in the tree
Node* dfs2(Node* root, int target)
{
if (root == 0)
return 0;
if (root->data == target)
return root;
Node* node1 = dfs2(root->left, target);
Node* node2 = dfs2(root->right, target);
if (node1 != 0)
return node1;
if (node2 != 0)
return node2;
}
// Function to find the sum at distance K
int sum_at_distK(Node* root, int target,
int k)
{
// Hash Table to store
// the parent of a node
unordered_map<Node*, Node*> par;
// Make the parent of root node as NULL
// since it does not have any parent
par[root] = 0;
// Mark the parent node for all the
// nodes using DFS
dfs(root, par);
// Find the target node in the tree
Node* node = dfs2(root, target);
// Hash Table to mark
// the visited nodes
unordered_map<Node*, int> vis;
int sum = 0;
// DFS call to find the sum
dfs3(node, 0, sum, k, vis, par);
return sum;
}
// Driver Code
int main()
{
// Taking Input
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(9);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(7);
root->left->left->left = new Node(8);
root->left->left->right = new Node(19);
root->right->right->left = new Node(20);
root->right->right->right
= new Node(11);
root->left->left->left->left
= new Node(30);
root->left->left->right->left
= new Node(40);
root->left->left->right->right
= new Node(50);
int target = 9, K = 1;
// Function call
cout << sum_at_distK(root, target, K);
return 0;
}
Java
// Java code to implement above approach
import java.util.*;
public class Main {
// Structure of a tree node
static class Node {
int data;
Node left;
Node right;
Node(int val)
{
this.data = val;
this.left = null;
this.right = null;
}
}
// Function for marking the parent node
// for all the nodes using DFS
static void dfs(Node root,
HashMap <Node, Node> par)
{
if (root == null)
return;
if (root.left != null)
par.put( root.left, root);
if (root.right != null)
par.put( root.right, root);
dfs(root.left, par);
dfs(root.right, par);
}
static int sum;
// Function calling for finding the sum
static void dfs3(Node root, int h, int k,
HashMap <Node, Integer> vis,
HashMap <Node, Node> par)
{
if (h == k + 1)
return;
if (root == null)
return;
if (vis.containsKey(root))
return;
sum += root.data;
vis.put(root, 1);
dfs3(root.left, h + 1, k, vis, par);
dfs3(root.right, h + 1, k, vis, par);
dfs3(par.get(root), h + 1, k, vis, par);
}
// Function for finding
// the target node in the tree
static Node dfs2(Node root, int target)
{
if (root == null)
return null;
if (root.data == target)
return root;
Node node1 = dfs2(root.left, target);
Node node2 = dfs2(root.right, target);
if (node1 != null)
return node1;
if (node2 != null)
return node2;
return null;
}
static int sum_at_distK(Node root, int target,
int k)
{
// Hash Map to store
// the parent of a node
HashMap <Node, Node> par = new HashMap<>();
// Make the parent of root node as NULL
// since it does not have any parent
par.put(root, null);
// Mark the parent node for all the
// nodes using DFS
dfs(root, par);
// Find the target node in the tree
Node node = dfs2(root, target);
// Hash Map to mark
// the visited nodes
HashMap <Node, Integer> vis = new HashMap<>();
sum = 0;
// DFS call to find the sum
dfs3(node, 0, k, vis, par);
return sum;
}
public static void main(String args[]) {
// Taking Input
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(9);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(19);
root.right.right.left = new Node(20);
root.right.right.right
= new Node(11);
root.left.left.left.left
= new Node(30);
root.left.left.right.left
= new Node(40);
root.left.left.right.right
= new Node(50);
int target = 9, K = 1;
// Function call
System.out.println( sum_at_distK(root, target, K) );
}
}
// This code has been contributed by Sachin Sahara (sachin801)
C#
// C# code to implement above approach
using System;
using System.Collections.Generic;
public class GFG {
// Structure of a tree node
class Node {
public int data;
public Node left;
public Node right;
public Node(int val)
{
this.data = val;
this.left = null;
this.right = null;
}
}
// Function for marking the parent node
// for all the nodes using DFS
static void dfs(Node root, Dictionary<Node, Node> par)
{
if (root == null)
return;
if (root.left != null)
par.Add(root.left, root);
if (root.right != null)
par.Add(root.right, root);
dfs(root.left, par);
dfs(root.right, par);
}
static int sum;
// Function calling for finding the sum
static void dfs3(Node root, int h, int k,
Dictionary<Node, int> vis,
Dictionary<Node, Node> par)
{
if (h == k + 1)
return;
if (root == null)
return;
if (vis.ContainsKey(root))
return;
sum += root.data;
vis.Add(root, 1);
dfs3(root.left, h + 1, k, vis, par);
dfs3(root.right, h + 1, k, vis, par);
dfs3(par[root], h + 1, k, vis, par);
}
// Function for finding
// the target node in the tree
static Node dfs2(Node root, int target)
{
if (root == null)
return null;
if (root.data == target)
return root;
Node node1 = dfs2(root.left, target);
Node node2 = dfs2(root.right, target);
if (node1 != null)
return node1;
if (node2 != null)
return node2;
return null;
}
static int sum_at_distK(Node root, int target, int k)
{
// Hash Map to store
// the parent of a node
Dictionary<Node, Node> par
= new Dictionary<Node, Node>();
// Make the parent of root node as NULL
// since it does not have any parent
par.Add(root, null);
// Mark the parent node for all the
// nodes using DFS
dfs(root, par);
// Find the target node in the tree
Node node = dfs2(root, target);
// Hash Map to mark
// the visited nodes
Dictionary<Node, int> vis
= new Dictionary<Node, int>();
sum = 0;
// DFS call to find the sum
dfs3(node, 0, k, vis, par);
return sum;
}
static public void Main()
{
// Code
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(9);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(19);
root.right.right.left = new Node(20);
root.right.right.right = new Node(11);
root.left.left.left.left = new Node(30);
root.left.left.right.left = new Node(40);
root.left.left.right.right = new Node(50);
int target = 9, K = 1;
// Function call
Console.Write(sum_at_distK(root, target, K));
}
}
// This code is contributed by lokesh(lokeshmvs21).
Producción
22
Complejidad del tiempo:O(N) donde N es el número de Nodes en el árbol
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA