Dado un árbol binario , la tarea es imprimir los Nodes medios de cada nivel de un árbol binario . Considerando que M es el número de Nodes en cualquier nivel, imprima (M/2) el Node si M es impar. De lo contrario, imprima (M/2) el Node y ((M/2) + 1) el Node .
Ejemplos:
Entrada: A continuación se muestra el árbol dado:
Salida:
1
2 3
5 10
11 6
7 9
Explicación:
Los Nodes medios de cada nivel son:
Nivel 0 – 1
Nivel 1 – 2 y 3
Nivel 2 – 5 y 10
Nivel 3 – 11 y 6
Nivel 4 – 7 y 9Entrada: A continuación se muestra el árbol dado:
Salida:
1
2 3
5
8 9
11
12 13
15 14
Explicación:
Los Nodes medios de cada nivel son:
Nivel 0 – 1
Nivel 1 – 2 y 3
Nivel 2 – 5
Nivel 3 – 8 y 9
Nivel 4 – 11
Nivel 5 – 12 y 13
Nivel 6 – 15 y 14
Enfoque: La idea es realizar el DFS Traversal en el Árbol dado y almacenar todos los Nodes para cada nivel en un mapa de vectores . Ahora recorra el Mapa e imprima los Nodes medios en consecuencia. A continuación se muestran los pasos:
- Inicialice un mapa de vectores M para almacenar todos los Nodes correspondientes a cada nivel en un vector.
- Realice DFS Traversal en el árbol dado comenzando con el nivel 0 y llame recursivamente al subárbol izquierdo y derecho con un incremento en el nivel de 1 .
- Almacena todos los Nodes en el DFS Traversal anterior correspondiente a cada nivel como M[level].push_back(root->data) .
- Ahora, recorra el Mapa M y para cada nivel haga lo siguiente:
- Encuentre el tamaño (digamos S ) del vector (digamos A ) asociado con cada nivel en el mapa M.
- Si S es impar, simplemente imprima el valor de A[(S – 1)/2] como el Node central (S/2) .
- De lo contrario, imprima el valor de A[(S – 1)/2] y A[(S – 1)/2 + 1] como el medio (S/2) th y ((S/2) + 1) th Node.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure Node of Binary Tree
struct node {
int data;
struct node* left;
struct node* right;
};
// Function to create a new node
struct node* newnode(int d)
{
struct node* temp
= (struct node*)malloc(
sizeof(struct node));
temp->data = d;
temp->left = NULL;
temp->right = NULL;
// Return the created node
return temp;
}
// Function that performs the DFS
// traversal on Tree to store all the
// nodes at each level in map M
void dfs(node* root, int l,
map<int, vector<int> >& M)
{
// Base Case
if (root == NULL)
return;
// Push the current level node
M[l].push_back(root->data);
// Left Recursion
dfs(root->left, l + 1, M);
// Right Recursion
dfs(root->right, l + 1, M);
}
// Function that print all the middle
// nodes for each level in Binary Tree
void printMidNodes(node* root)
{
// Stores all node in each level
map<int, vector<int> > M;
// Perform DFS traversal
dfs(root, 0, M);
// Traverse the map M
for (auto& it : M) {
// Get the size of vector
int size = it.second.size();
// For odd number of elements
if (size & 1) {
// Print (M/2)th Element
cout << it.second[(size - 1) / 2]
<< endl;
}
// Otherwise
else {
// Print (M/2)th and
// (M/2 + 1)th Element
cout << it.second[(size - 1) / 2]
<< ' '
<< it.second[(size - 1) / 2 + 1]
<< endl;
}
}
}
// Driver Code
int main()
{
/*
Binary tree shown below is:
1
/ \
2 3
/ \ / \
4 5 10 8
/ \
11 6
/ \
7 9
*/
// Given Tree
struct node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->left->right->left = newnode(11);
root->left->right->right = newnode(6);
root->left->right->right->left = newnode(7);
root->left->right->right->right = newnode(9);
root->right->left = newnode(10);
root->right->right = newnode(8);
// Function Call
printMidNodes(root);
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
static Map<Integer, Vector<Integer> > M;
// Structure Node of
// Binary Tree
static class node
{
int data;
node left;
node right;
public node() {}
public node(int data,
node left,
node right)
{
super();
this.data = data;
this.left = left;
this.right = right;
}
};
// Function to create a new node
static node newnode(int d)
{
node temp = new node();
temp.data = d;
temp.left = null;
temp.right = null;
// Return the created node
return temp;
}
// Function that performs the DFS
// traversal on Tree to store all the
// nodes at each level in map M
static void dfs(node root, int l)
{
// Base Case
if (root == null)
return;
// Push the current level node
if(!M.containsKey(l))
{
Vector<Integer> temp = new Vector<Integer>();
temp.add(root.data);
M.put(l, temp);
}
else
M.get(l).add(root.data);
// Left Recursion
dfs(root.left, l + 1);
// Right Recursion
dfs(root.right, l + 1);
}
// Function that print all the middle
// nodes for each level in Binary Tree
static void printMidNodes(node root)
{
// Stores all node in each level
M = new HashMap<Integer,
Vector<Integer> >();
// Perform DFS traversal
dfs(root, 0);
// Traverse the map M
for (Map.Entry<Integer,
Vector<Integer>> it : M.entrySet())
{
// Get the size of vector
int size = it.getValue().size();
// For odd number of elements
if (size % 2 == 1)
{
// Print (M/2)th Element
System.out.print(it.getValue().get((size - 1) / 2) + "\n");
}
// Otherwise
else
{
// Print (M/2)th and
// (M/2 + 1)th Element
System.out.print(it.getValue().get((size - 1) / 2) + " " +
it.getValue().get(((size - 1) / 2) + 1) + "\n");
}
}
}
// Driver Code
public static void main(String[] args)
{
/*
Binary tree shown below is:
1
/ \
2 3
/ \ / \
4 5 10 8
/ \
11 6
/ \
7 9
*/
// Given Tree
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
root.left.right.left = newnode(11);
root.left.right.right = newnode(6);
root.left.right.right.left = newnode(7);
root.left.right.right.right = newnode(9);
root.right.left = newnode(10);
root.right.right = newnode(8);
// Function Call
printMidNodes(root);
}
}
//This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Structure Node of Binary Tree class node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to create a new node def newnode(d): temp = node(d) # Return the created node return temp # Function that performs the DFS # traversal on Tree to store all the # nodes at each level in map M def dfs(root, l, M): # Base Case if (root == None): return # Push the current level node if l not in M: M[l] = [] M[l].append(root.data) # Left Recursion dfs(root.left, l + 1, M) # Right Recursion dfs(root.right, l + 1, M) # Function that print all the middle # nodes for each level in Binary Tree def printMidNodes(root): # Stores all node in each level M = dict() # Perform DFS traversal dfs(root, 0, M) # Traverse the map M for it in M.values(): # Get the size of vector size = len(it) # For odd number of elements if (size & 1): # Print (M/2)th Element print(it[(size - 1) // 2]) # Otherwise else: # Print (M/2)th and # (M/2 + 1)th Element print(str(it[(size - 1) // 2]) + ' ' + str(it[(size - 1) // 2 + 1])) # Driver Code if __name__=="__main__": ''' Binary tree shown below is: 1 / \ 2 3 / \ / \ 4 5 10 8 / \ 11 6 / \ 7 9 ''' # Given Tree root = newnode(1) root.left = newnode(2) root.right = newnode(3) root.left.left = newnode(4) root.left.right = newnode(5) root.left.right.left = newnode(11) root.left.right.right = newnode(6) root.left.right.right.left = newnode(7) root.left.right.right.right = newnode(9) root.right.left = newnode(10) root.right.right = newnode(8) # Function Call printMidNodes(root) # This code is contributed by rutvik_56
C#
// C# program for
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
static Dictionary<int,ArrayList> M;
// Structure Node of
// Binary Tree
class node
{
public int data;
public node left;
public node right;
public node(int data,
node left,
node right)
{
this.data = data;
this.left = left;
this.right = right;
}
};
// Function to create a new node
static node newnode(int d)
{
node temp = new node(d, null, null);
// Return the created node
return temp;
}
// Function that performs the DFS
// traversal on Tree to store all the
// nodes at each level in map M
static void dfs(node root, int l)
{
// Base Case
if (root == null)
return;
// Push the current level node
if(!M.ContainsKey(l))
{
ArrayList temp = new ArrayList();
temp.Add(root.data);
M[l] = temp;
}
else
M[l].Add(root.data);
// Left Recursion
dfs(root.left, l + 1);
// Right Recursion
dfs(root.right, l + 1);
}
// Function that print all the middle
// nodes for each level in Binary Tree
static void printMidNodes(node root)
{
// Stores all node in each level
M = new Dictionary<int, ArrayList>();
// Perform DFS traversal
dfs(root, 0);
// Traverse the map M
foreach (KeyValuePair<int,ArrayList> it in M)
{
// Get the size of vector
int size = it.Value.Count;
// For odd number of elements
if (size % 2 == 1)
{
// Print (M/2)th Element
Console.Write(it.Value[(size - 1) / 2] + "\n");
}
// Otherwise
else
{
// Print (M/2)th and
// (M/2 + 1)th Element
Console.Write(it.Value[(size - 1) / 2] + " " +
it.Value[((size - 1) / 2) + 1] + "\n");
}
}
}
// Driver Code
public static void Main(string[] args)
{
/*
Binary tree shown below is:
1
/ \
2 3
/ \ / \
4 5 10 8
/ \
11 6
/ \
7 9
*/
// Given Tree
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
root.left.right.left = newnode(11);
root.left.right.right = newnode(6);
root.left.right.right.left = newnode(7);
root.left.right.right.right = newnode(9);
root.right.left = newnode(10);
root.right.right = newnode(8);
// Function Call
printMidNodes(root);
}
}
// This code is contributed by pratham76
Javascript
<script>
// Javascript program for
// the above approach
var M = new Map();
// Structure Node of
// Binary Tree
class node
{
constructor(data, left, right)
{
this.data = data;
this.left = left;
this.right = right;
}
};
// Function to create a new node
function newnode(d)
{
var temp = new node(d, null, null);
// Return the created node
return temp;
}
// Function that performs the DFS
// traversal on Tree to store all the
// nodes at each level in map M
function dfs(root, l)
{
// Base Case
if (root == null)
return;
// Push the current level node
if (!M.has(l))
{
var temp = [];
temp.push(root.data);
M.set(l, temp);
}
else
{
var temp = M.get(l);
temp.push(root.data);
M.set(l, temp);
}
// Left Recursion
dfs(root.left, l + 1);
// Right Recursion
dfs(root.right, l + 1);
}
// Function that print all the middle
// nodes for each level in Binary Tree
function printMidNodes(root)
{
// Stores all node in each level
M = new Map();
// Perform DFS traversal
dfs(root, 0);
// Traverse the map M
M.forEach((value,key) => {
// Get the size of vector
var size = value.length;
// For odd number of elements
if (size % 2 == 1)
{
// Print (M/2)th Element
document.write(value[parseInt(
(size - 1) / 2)] + "<br>");
}
// Otherwise
else
{
// Print (M/2)th and
// (M/2 + 1)th Element
document.write(value[parseInt((size - 1) / 2)] + " " +
value[parseInt(((size - 1) / 2) + 1)] + "<br>");
}
});
}
// Driver Code
/*
Binary tree shown below is:
1
/ \
2 3
/ \ / \
4 5 10 8
/ \
11 6
/ \
7 9
*/
// Given Tree
var root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
root.left.right.left = newnode(11);
root.left.right.right = newnode(6);
root.left.right.right.left = newnode(7);
root.left.right.right.right = newnode(9);
root.right.left = newnode(10);
root.right.right = newnode(8);
// Function Call
printMidNodes(root);
// This code is contributed by noob2000
</script>
Producción:
1 2 3 5 10 11 6 7 9
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sunilkannur98 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA