Dadas dos arrays Node_ID[] y Parent_ID[]. , construya un árbol binario donde el valor del i -ésimo Node sea igual a Node_ID[i] y el padre del i -ésimo Node sea Parent_ID[i] . Dado un Node X , la tarea es imprimir los valores de los Nodes del árbol con raíz en X.
Ejemplos :
Entrada: Node_ID[]= [11, 48, 100, 5], Parent_ID[] = [48, 0, 5, 48], X = 5
Salida: [5, 100]
Explicación:
El árbol construido es el siguiente:
48
/ \
11 5
/
100
Por lo tanto, el subárbol del Node 5 contiene los Nodes {5, 100}.Entrada : Node_ID[] = [1, 2, 3], Parent_ID[] = [0, 1, 1], X = 2
Salida : [2]
Enfoque ingenuo : siga los pasos a continuación para resolver el problema
- Construya una estructura de árbol a partir de Node_ID[] y Parent_ID[]
- Almacene los Nodes con el padre X en el árbol vectorial
- Para cada Node, verifique si X es un ancestro de ese Node
- Si se determina que es cierto, almacene el Node en el árbol vectorial . De lo contrario, continúe.
- Imprime los Nodes presentes en el árbol vectorial.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to print nodes
// in the tree rooted at x
void subtreeX(vector<int>& nid,
vector<int>& pid, int x)
{
unordered_map<int, int> parent;
vector<int> tree;
// Map every node to its parent
for (int i = 0; i < nid.size(); i++) {
parent[nid[i]] = pid[i];
}
// Subtree with x as root
tree.push_back(x);
for (int i = 0; i < nid.size(); i++) {
int k = nid[i];
int p = k;
// Iterate until k becomes
// equal to the root
while (k != 0) {
if (parent[k] == x) {
// x is an ancestor of nid[i]
tree.push_back(nid[i]);
break;
}
k = parent[k];
}
}
// Print elements in the subtree
for (int node : tree)
cout << node << " ";
}
// Driver Code
int main()
{
vector<int> nid = { 11, 48, 100, 5 };
vector<int> pid = { 48, 0, 5, 48 };
int x = 5;
// Function call to print nodes
// in the tree rooted at x
subtreeX(nid, pid, x);
return 0;
}
Java
import java.util.*;
class GFG
{
// Function to print nodes
// in the tree rooted at x
static void subtreeX(int[] nid, int[] pid, int x)
{
HashMap<Integer, Integer> parent
= new HashMap<Integer, Integer>();
List<Integer> tree = new LinkedList<>();
// Map every node to its parent
for (int i = 0; i < nid.length; i++)
{
parent.put(nid[i], pid[i]);
}
// Subtree with x as root
tree.add(x);
for (int i = 0; i < nid.length; i++)
{
int k = nid[i];
int p = k;
// Iterate until k becomes
// equal to the root
while (k != 0)
{
if (parent.containsKey(k) && parent.get(k) == x)
{
// x is an ancestor of nid[i]
tree.add(nid[i]);
break;
}
k = parent.containsKey(k) ? parent.get(k) : -1;
}
}
// Print elements in the subtree
for (int node : tree)
System.out.print(node + " ");
}
// Driver Code
public static void main(String[] args)
{
int[] nid = { 11, 48, 100, 5 };
int[] pid = { 48, 0, 5, 48 };
int x = 5;
// Function call to print nodes
// in the tree rooted at x
subtreeX(nid, pid, x);
}
}
// This code is contributed by 29AjayKumar
Python3
# Function to print nodes
# in the tree rooted at x
def subtreeX(nid, pid, x):
parent = {}
tree = []
# Map every node to its parent
for i in range(len(nid)):
parent[nid[i]] = pid[i]
# Subtree with x as root
tree.append(x)
for i in range(len(nid)):
k = nid[i]
p = k
# Iterate until k becomes
# equal to the root
while (k != 0):
if (parent[k] == x):
# x is an ancestor of nid[i]
tree.append(nid[i])
break
k = parent[k]
# Print elements in the subtree
for node in tree:
print(node, end = " ")
# Driver Code
if __name__ == '__main__':
nid = [11, 48, 100, 5]
pid = [48, 0, 5, 48 ]
x = 5
# Function call to print nodes
# in the tree rooted at x
subtreeX(nid, pid, x)
# This code is contributed by mohit kumar 29.
C#
using System;
using System.Collections.Generic;
public class GFG
{
// Function to print nodes
// in the tree rooted at x
static void subtreeX(int[] nid, int[] pid, int x)
{
Dictionary<int, int> parent
= new Dictionary<int, int>();
List<int> tree = new List<int>();
// Map every node to its parent
for (int i = 0; i < nid.Length; i++)
{
parent.Add(nid[i], pid[i]);
}
// Subtree with x as root
tree.Add(x);
for (int i = 0; i < nid.Length; i++)
{
int k = nid[i];
int p = k;
// Iterate until k becomes
// equal to the root
while (k != 0)
{
if (parent.ContainsKey(k) && parent[k] == x)
{
// x is an ancestor of nid[i]
tree.Add(nid[i]);
break;
}
k = parent.ContainsKey(k) ? parent[k] : -1;
}
}
// Print elements in the subtree
foreach (int node in tree)
Console.Write(node + " ");
}
// Driver Code
public static void Main(String[] args)
{
int[] nid = { 11, 48, 100, 5 };
int[] pid = { 48, 0, 5, 48 };
int x = 5;
// Function call to print nodes
// in the tree rooted at x
subtreeX(nid, pid, x);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Function to print nodes
// in the tree rooted at x
function subtreeX(nid, pid, x)
{
var parent = new Map();
var tree = [];
// Map every node to its parent
for (var i = 0; i < nid.length; i++)
{
parent.set(nid[i], pid[i]);
}
// Subtree with x as root
tree.push(x);
for (var i = 0; i < nid.length; i++)
{
var k = nid[i];
var p = k;
// Iterate until k becomes
// equal to the root
while (k != 0)
{
if (parent.has(k) && parent.get(k) == x)
{
// x is an ancestor of nid[i]
tree.push(nid[i]);
break;
}
k = parent.has(k) ? parent.get(k) : -1;
}
}
// Print elements in the subtree
for(var node of tree)
document.write(node + " ");
}
// Driver Code
var nid = [11, 48, 100, 5];
var pid = [48, 0, 5, 48];
var x = 5;
// Function call to print nodes
// in the tree rooted at x
subtreeX(nid, pid, x);
</script>
Producción:
5 100
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(N)
Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:
- Construya una estructura de árbol a partir de Node_ID[] y Parent_ID[]
- Realice DFS desde el Node X.
- Almacene los Nodes en un árbol vectorial
- Imprime los Nodes presentes en el árbol vectorial .
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// DFS to traverse subtree rooted at x
void dfs(int x, vector<int>& tree,
map<int, vector<int> >& child)
{
// Push x into the vector
tree.push_back(x);
// Check if x is a leaf node
if (child.find(x) != child.end()) {
// Recursively call dfs
// for children of x
for (int next : child[x]) {
dfs(next, tree, child);
}
}
}
// Function to print nodes
// in the tree rooted at x
void SubtreeX(vector<int>& nid,
vector<int>& pid, int x)
{
int n = nid.size();
map<int, vector<int> > child;
// adding edges in a tree
for (int i = 0; i < n; i++) {
if (child.find(pid[i])
== child.end()) {
// Initialize adjacency list
child[pid[i]] = vector<int>();
}
child[pid[i]].push_back(nid[i]);
}
// Stores nodes in the subtree
vector<int> tree;
// Perform DFS from node x
dfs(x, tree, child);
for (int node : tree) {
cout << node << " ";
}
}
// Driver Code
int main()
{
vector<int> nid = { 11, 48, 100, 5 };
vector<int> pid = { 48, 0, 5, 48 };
int x = 5;
// Function call to print nodes
// in the tree rooted at x
SubtreeX(nid, pid, x);
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG{
// DFS to traverse subtree rooted at x
static void dfs(int x, Vector<Integer> tree,
Map<Integer, Vector<Integer>> child)
{
// Push x into the vector
tree.add(x);
// Check if x is a leaf node
if (child.containsKey(x))
{
// Recursively call dfs
// for children of x
for(int next : child.get(x))
{
dfs(next, tree, child);
}
}
}
// Function to print nodes
// in the tree rooted at x
static void SubtreeX(Vector<Integer> nid,
Vector<Integer> pid, int x)
{
int n = nid.size();
Map<Integer, Vector<Integer>> child = new HashMap<>();
// Adding edges in a tree
for(int i = 0; i < n; i++)
{
if (!child.containsKey(pid.get(i)))
{
// Initialize adjacency list
child.put(pid.get(i), new Vector<Integer>());
}
child.get(pid.get(i)).add(nid.get(i));
}
// Stores nodes in the subtree
Vector<Integer> tree = new Vector<Integer>();
// Perform DFS from node x
dfs(x, tree, child);
for(int node : tree)
{
System.out.print(node + " ");
}
}
// Driver Code
public static void main (String[] args)
{
Vector<Integer> nid = new Vector<Integer>(
Arrays.asList(11, 48, 100, 5));
Vector<Integer> pid = new Vector<Integer>(
Arrays.asList(48, 0, 5, 48));
int x = 5;
// Function call to print nodes
// in the tree rooted at x
SubtreeX(nid, pid, x);
}
}
// This code is contributed by rag2127
Python3
# DFS to traverse subtree rooted at x
def dfs(x, tree, child):
# Push x into the vector
tree.append(x)
# Check if x is a leaf node
if x in child:
# Recursively call dfs
# for children of x
for nextt in child[x]:
dfs(nextt, tree, child)
# Function to print nodes
# in the tree rooted at x
def SubtreeX(nid,pid,x):
n = len(nid)
child = {}
# Adding edges in a tree
for i in range(n):
if pid[i] not in child:
# Initialize adjacency list
child[pid[i]] = []
child[pid[i]].append(nid[i])
# Stores nodes in the subtree
tree = []
# Perform DFS from node x
dfs(x, tree, child)
print(*tree)
# Driver Code
nid = [11, 48, 100, 5]
pid = [48, 0, 5, 48]
x = 5
# Function call to print nodes
# in the tree rooted at x
SubtreeX(nid, pid, x)
# This code is contributed by avanitrachhadiya2155
C#
using System;
using System.Collections.Generic;
class GFG {
// DFS to traverse subtree rooted at x
static void dfs(int x, List<int> tree,
Dictionary<int, List<int>> child)
{
// Push x into the vector
tree.Add(x);
// Check if x is a leaf node
if (child.ContainsKey(x))
{
// Recursively call dfs
// for children of x
foreach(int next in child[x])
{
dfs(next, tree, child);
}
}
}
// Function to print nodes
// in the tree rooted at x
static void SubtreeX(List<int> nid, List<int> pid, int x)
{
int n = nid.Count;
Dictionary<int, List<int>> child = new Dictionary<int, List<int>>();
// Adding edges in a tree
for(int i = 0; i < n; i++)
{
if (!child.ContainsKey(pid[i]))
{
// Initialize adjacency list
child[pid[i]] = new List<int>();
}
child[pid[i]].Add(nid[i]);
}
// Stores nodes in the subtree
List<int> tree = new List<int>();
// Perform DFS from node x
dfs(x, tree, child);
foreach(int node in tree)
{
Console.Write(node + " ");
}
}
// Driver code
static void Main() {
List<int> nid = new List<int>{11, 48, 100, 5};
List<int> pid = new List<int>{48, 0, 5, 48};
int x = 5;
// Function call to print nodes
// in the tree rooted at x
SubtreeX(nid, pid, x);
}
}
// This code is contributed by decode2207.
Javascript
<script>
// DFS to traverse subtree rooted at x
function dfs(x,tree,child)
{
// Push x into the vector
tree.push(x);
// Check if x is a leaf node
if (child.has(x))
{
// Recursively call dfs
// for children of x
for(let next=0;next< child.get(x).length;next++)
{
dfs(child.get(x)[next], tree, child);
}
}
}
// Function to print nodes
// in the tree rooted at x
function SubtreeX(nid,pid,x)
{
let n = nid.length;
let child = new Map();
// Adding edges in a tree
for(let i = 0; i < n; i++)
{
if (!child.has(pid[i]))
{
// Initialize adjacency list
child.set(pid[i], []);
}
child.get(pid[i]).push(nid[i]);
}
// Stores nodes in the subtree
let tree = [];
// Perform DFS from node x
dfs(x, tree, child);
for(let node=0;node< tree.length;node++)
{
document.write(tree[node] + " ");
}
}
// Driver Code
let nid = [11, 48, 100, 5];
let pid = [48, 0, 5, 48];
let x = 5;
// Function call to print nodes
// in the tree rooted at x
SubtreeX(nid, pid, x);
// This code is contributed by unknown2108
</script>
Producción:
5 100
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por rutvikchandla3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA