Dado un árbol binario que consta de N Nodes con valores en el rango [1, N] , la tarea es encontrar la distancia desde el Node raíz hasta cada Node del árbol.
Ejemplos:
Aporte:
1 / \ 2 3 / \ \ 4 5 6Salida: 0 1 1 2 2 2
Explicación:
La distancia desde la raíz hasta el Node 1 es 0.
La distancia desde la raíz hasta el Node 2 es 1.
La distancia desde la raíz hasta el Node 3 es 1.
La distancia desde la raíz hasta el Node 4 es 2.
La distancia de la raíz al Node 5 es 2.
La distancia de la raíz al Node 6 es 2.
Aporte:
5 / \ 4 6 / \ 3 7 / \ 1 2Salida: 3 3 2 1 0 1 2
Enfoque: El problema se puede resolver utilizando la técnica BFS . La idea es utilizar el hecho de que la distancia desde la raíz hasta un Node es igual al nivel de ese Node en el árbol binario . Siga los pasos a continuación para resolver el problema:
- Inicialice una cola, digamos Q , para almacenar los Nodes en cada nivel del árbol.
- Inicialice una array, digamos dist[] , donde dist[i] almacena la distancia desde el Node raíz hasta el i -ésimo del árbol.
- Atraviesa el árbol usando BFS . Por cada i -ésimo Node encontrado, actualice dist[i] al nivel de ese Node en el árbol binario.
- Finalmente, imprima la array dist[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
struct Node {
// Stores data value
// of the node
int data;
// Stores left subtree
// of a node
Node* left;
// Stores right subtree
// of a node
Node* right;
Node(int x)
{
data = x;
left = right = NULL;
}
};
void findDistance(Node* root, int N)
{
// Store nodes at each level
// of the binary tree
queue<Node*> Q;
// Insert root into Q
Q.push(root);
// Stores level of a node
int level = 0;
// dist[i]: Stores the distance
// from root node to node i
int dist[N + 1];
// Traverse tree using BFS
while (!Q.empty()) {
// Stores count of nodes
// at current level
int M = Q.size();
// Traverse the nodes at
// current level
for (int i = 0; i < M; i++) {
// Stores front element
// of the queue
root = Q.front();
// Pop front element
// of the queue
Q.pop();
// Stores the distance from
// root node to current node
dist[root->data] = level;
if (root->left) {
// Push left subtree
Q.push(root->left);
}
if (root->right) {
// Push right subtree
Q.push(root->right);
}
}
// Update level
level += 1;
}
for (int i = 1; i <= N; i++) {
cout << dist[i] << " ";
}
}
// Driver Code
int main()
{
int N = 7;
Node* root = new Node(5);
root->left = new Node(4);
root->right = new Node(6);
root->left->left = new Node(3);
root->left->right = new Node(7);
root->left->left->left = new Node(1);
root->left->left->right = new Node(2);
findDistance(root, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
static class Node
{
// Stores data value
// of the node
int data;
// Stores left subtree
// of a node
Node left;
// Stores right subtree
// of a node
Node right;
Node(int x)
{
data = x;
left = right = null;
}
};
static void findDistance(Node root, int N)
{
// Store nodes at each level
// of the binary tree
Queue<Node> Q = new LinkedList<>();
// Insert root into Q
Q.add(root);
// Stores level of a node
int level = 0;
// dist[i]: Stores the distance
// from root node to node i
int []dist = new int[N + 1];
// Traverse tree using BFS
while (!Q.isEmpty())
{
// Stores count of nodes
// at current level
int M = Q.size();
// Traverse the nodes at
// current level
for (int i = 0; i < M; i++)
{
// Stores front element
// of the queue
root = Q.peek();
// Pop front element
// of the queue
Q.remove();
// Stores the distance from
// root node to current node
dist[root.data] = level;
if (root.left != null)
{
// Push left subtree
Q.add(root.left);
}
if (root.right != null)
{
// Push right subtree
Q.add(root.right);
}
}
// Update level
level += 1;
}
for (int i = 1; i <= N; i++)
{
System.out.print(dist[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int N = 7;
Node root = new Node(5);
root.left = new Node(4);
root.right = new Node(6);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.left.left.left = new Node(1);
root.left.left.right = new Node(2);
findDistance(root, N);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to implement # the above approach class Node: def __init__(self, data): # Stores data value # of the node self.data = data # Stores left subtree # of a node self.left = None # Stores right subtree # of a node self.right = None def findDistance(root, N): # Store nodes at each level # of the binary tree Q = [] # Insert root into Q Q.append(root) # Stores level of a node level = 0 # dist[i]: Stores the distance # from root node to node i dist = [0 for i in range(N + 1)] # Traverse tree using BFS while Q: # Stores count of nodes # at current level M = len(Q) # Traverse the nodes at # current level for i in range(0, M): # Stores front element # of the queue root = Q[0] # Pop front element # of the queue Q.pop(0) # Stores the distance from # root node to current node dist[root.data] = level if root.left: # Push left subtree Q.append(root.left) if root.right: # Push right subtree Q.append(root.right) # Update level level += 1 for i in range(1, N + 1): print(dist[i], end = " ") # Driver code if __name__ == '__main__': N = 7 root = Node(5) root.left = Node(4) root.right = Node(6) root.left.left = Node(3) root.left.right = Node(7) root.left.left.left = Node(1) root.left.left.right = Node(2) findDistance(root, N) # This code is contributed by MuskanKalra1
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
class Node
{
// Stores data value
// of the node
public int data;
// Stores left subtree
// of a node
public Node left;
// Stores right subtree
// of a node
public Node right;
public Node(int x)
{
data = x;
left = right = null;
}
};
static void findDistance(Node root, int N)
{
// Store nodes at each level
// of the binary tree
Queue<Node> Q = new Queue<Node>();
// Insert root into Q
Q.Enqueue(root);
// Stores level of a node
int level = 0;
// dist[i]: Stores the distance
// from root node to node i
int []dist = new int[N + 1];
// Traverse tree using BFS
while (Q.Count != 0)
{
// Stores count of nodes
// at current level
int M = Q.Count;
// Traverse the nodes at
// current level
for (int i = 0; i < M; i++)
{
// Stores front element
// of the queue
root = Q.Peek();
// Pop front element
// of the queue
Q.Dequeue();
// Stores the distance from
// root node to current node
dist[root.data] = level;
if (root.left != null)
{
// Push left subtree
Q.Enqueue(root.left);
}
if (root.right != null)
{
// Push right subtree
Q.Enqueue(root.right);
}
}
// Update level
level += 1;
}
for (int i = 1; i <= N; i++)
{
Console.Write(dist[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int N = 7;
Node root = new Node(5);
root.left = new Node(4);
root.right = new Node(6);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.left.left.left = new Node(1);
root.left.left.right = new Node(2);
findDistance(root, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program to implement the above approach
// Structure of a tree node
class Node
{
constructor(x) {
this.left = null;
this.right = null;
this.data = x;
}
}
function findDistance(root, N)
{
// Store nodes at each level
// of the binary tree
let Q = [];
// Insert root into Q
Q.push(root);
// Stores level of a node
let level = 0;
// dist[i]: Stores the distance
// from root node to node i
let dist = new Array(N + 1);
// Traverse tree using BFS
while (Q.length > 0)
{
// Stores count of nodes
// at current level
let M = Q.length;
// Traverse the nodes at
// current level
for (let i = 0; i < M; i++)
{
// Stores front element
// of the queue
root = Q[0];
// Pop front element
// of the queue
Q.shift();
// Stores the distance from
// root node to current node
dist[root.data] = level;
if (root.left != null)
{
// Push left subtree
Q.push(root.left);
}
if (root.right != null)
{
// Push right subtree
Q.push(root.right);
}
}
// Update level
level += 1;
}
for (let i = 1; i <= N; i++)
{
document.write(dist[i] + " ");
}
}
let N = 7;
let root = new Node(5);
root.left = new Node(4);
root.right = new Node(6);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.left.left.left = new Node(1);
root.left.left.right = new Node(2);
findDistance(root, N);
</script>
Producción:
3 3 2 1 0 1 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)