Dado un árbol binario , la tarea es eliminar todos los subárboles que no contienen ningún Node de valor impar. Imprima el recorrido de orden de nivel del árbol después de eliminar estos subárboles.
Nota: Imprima NULL para los Nodes eliminados.
Ejemplos:
Entrada: A continuación se muestra el Árbol dado:
1
\
2
/ \
8 5
Salida: 1 NULL 2 NULL 5
Explicación:
Árbol después de la poda:
1
\
2
\
5Entrada: A continuación se muestra el Árbol dado:
1
/ \
2 7
/ \ / \
8 10 12 5
Salida: 1 NULL 7 NULL 5
Explicación:
Árbol después de la poda:
1
\
7
\
5
Enfoque: Para resolver el problema dado, la idea es atravesar el árbol utilizando DFS Traversal y se utilizará un concepto de retroceso . Siga los pasos a continuación para resolver el problema:
- Recorra el árbol dado usando DFS Traversal y realice los siguientes pasos:
- Si el Node raíz es NULL , entonces regrese.
- Si el valor del Node hoja es par, elimine este Node devolviendo NULL . De lo contrario, devuelva el Node raíz de la llamada recursiva actual.
- Actualice recursivamente los subárboles izquierdo y derecho usando las condiciones anteriores.
- Después de completar los pasos anteriores, imprima el árbol actualizado utilizando el orden de niveles Traversal con NULL en lugar de los Nodes eliminados.
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;
// Node of the tree
struct node {
int data;
struct node *left, *right;
};
// Function to create a new node
node* newNode(int key)
{
node* temp = new node;
temp->data = key;
temp->left = temp->right = NULL;
return (temp);
}
// Function to print tree level wise
void printLevelOrder(node* root)
{
// Base Case
if (!root)
return;
// Create an empty queue for
// level order traversal
queue<node*> q;
// Enqueue Root
q.push(root);
while (!q.empty()) {
// Print front of queue and
// remove it from queue
node* temp = q.front();
cout << temp->data << " ";
q.pop();
// If left child is present
if (temp->left != NULL) {
q.push(temp->left);
}
// Otherwise
else if (temp->right != NULL) {
cout << "NULL ";
}
// If right child is present
if (temp->right != NULL) {
q.push(temp->right);
}
// Otherwise
else if (temp->left != NULL) {
cout << "NULL ";
}
}
}
// Function to remove subtrees
node* pruneTree(node* root)
{
// Base Case
if (!root) {
return NULL;
}
// Search for required condition
// in left and right half
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
// If the node is even
// and leaf node
if (root->data % 2 == 0
&& !root->right
&& !root->left)
return NULL;
return root;
}
// Driver Code
int main()
{
struct node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(8);
root->left->right = newNode(10);
root->right = newNode(7);
root->right->left = newNode(12);
root->right->right = newNode(5);
// Function Call
node* newRoot = pruneTree(root);
// Print answer
printLevelOrder(newRoot);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Node of the tree
static class node
{
int data;
node left, right;
};
// Function to create a new node
static node newNode(int key)
{
node temp = new node();
temp.data = key;
temp.left = temp.right = null;
return (temp);
}
// Function to print tree level wise
static void printLevelOrder(node root)
{
// Base Case
if (root==null)
return;
// Create an empty queue for
// level order traversal
Queue<node> q = new LinkedList<>();
// Enqueue Root
q.add(root);
while (!q.isEmpty())
{
// Print front of queue and
// remove it from queue
node temp = q.peek();
System.out.print(temp.data+ " ");
q.remove();
// If left child is present
if (temp.left != null)
{
q.add(temp.left);
}
// Otherwise
else if (temp.right != null)
{
System.out.print("null ");
}
// If right child is present
if (temp.right != null)
{
q.add(temp.right);
}
// Otherwise
else if (temp.left != null)
{
System.out.print("null ");
}
}
}
// Function to remove subtrees
static node pruneTree(node root)
{
// Base Case
if (root == null)
{
return null;
}
// Search for required condition
// in left and right half
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
// If the node is even
// and leaf node
if (root.data % 2 == 0
&& root.right==null
&& root.left==null)
return null;
return root;
}
// Driver Code
public static void main(String[] args)
{
node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(8);
root.left.right = newNode(10);
root.right = newNode(7);
root.right.left = newNode(12);
root.right.right = newNode(5);
// Function Call
node newRoot = pruneTree(root);
// Print answer
printLevelOrder(newRoot);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 program for the above approach
# Node of the tree
class node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
# Function to print tree level wise
def printLevelOrder(root):
# Base Case
if (root==None):
return
# Create an empty queue for
# level order traversal
q = []
# Enqueue Root
q.append(root)
while(len(q)>0):
# Print front of queue and
# remove it from queue
temp = q[0]
print(temp.data,end = " ")
q = q[1:]
# If left child is present
if (temp.left != None):
q.append(temp.left)
# Otherwise
elif (temp.right != None):
print("NULL",end= " ")
# If right child is present
if (temp.right != None):
q.append(temp.right)
# Otherwise
elif (temp.left != None):
print("NULL",end = " ")
# Function to remove subtrees
def pruneTree(root):
# Base Case
if (root==None):
return None
# Search for required condition
# in left and right half
root.left = pruneTree(root.left)
root.right = pruneTree(root.right)
# If the node is even
# and leaf node
if (root.data % 2 == 0 and root.right == None and root.left==None):
return None
return root
# Driver Code
if __name__ == '__main__':
root = node(1)
root.left = node(2)
root.left.left = node(8)
root.left.right = node(10)
root.right = node(7)
root.right.left = node(12)
root.right.right = node(5)
# Function Call
newRoot = pruneTree(root)
# Print answer
printLevelOrder(newRoot)
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Node of the tree
class node
{
public int data;
public node left, right;
};
// Function to create a new node
static node newNode(int key)
{
node temp = new node();
temp.data = key;
temp.left = temp.right = null;
return (temp);
}
// Function to print tree level wise
static void printLevelOrder(node root)
{
// Base Case
if (root == null)
return;
// Create an empty queue for
// level order traversal
Queue<node> q = new Queue<node>();
// Enqueue Root
q.Enqueue(root);
while (q.Count != 0)
{
// Print front of queue and
// remove it from queue
node temp = q.Peek();
Console.Write(temp.data+ " ");
q.Dequeue();
// If left child is present
if (temp.left != null)
{
q.Enqueue(temp.left);
}
// Otherwise
else if (temp.right != null)
{
Console.Write("null ");
}
// If right child is present
if (temp.right != null)
{
q.Enqueue(temp.right);
}
// Otherwise
else if (temp.left != null)
{
Console.Write("null ");
}
}
}
// Function to remove subtrees
static node pruneTree(node root)
{
// Base Case
if (root == null)
{
return null;
}
// Search for required condition
// in left and right half
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
// If the node is even
// and leaf node
if (root.data % 2 == 0
&& root.right==null
&& root.left==null)
return null;
return root;
}
// Driver Code
public static void Main(String[] args)
{
node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(8);
root.left.right = newNode(10);
root.right = newNode(7);
root.right.left = newNode(12);
root.right.right = newNode(5);
// Function Call
node newRoot = pruneTree(root);
// Print answer
printLevelOrder(newRoot);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Node of the tree
class node
{
constructor(key) {
this.left = null;
this.right = null;
this.data = key;
}
}
// Function to create a new node
function newNode(key)
{
let temp = new node(key);
return (temp);
}
// Function to print tree level wise
function printLevelOrder(root)
{
// Base Case
if (root == null)
return;
// Create an empty queue for
// level order traversal
let q = [];
// Enqueue Root
q.push(root);
while (q.length != 0)
{
// Print front of queue and
// remove it from queue
let temp = q[0];
document.write(temp.data+ " ");
q.shift();
// If left child is present
if (temp.left != null)
{
q.push(temp.left);
}
// Otherwise
else if (temp.right != null)
{
document.write("Null ");
}
// If right child is present
if (temp.right != null)
{
q.push(temp.right);
}
// Otherwise
else if (temp.left != null)
{
document.write("Null ");
}
}
}
// Function to remove subtrees
function pruneTree(root)
{
// Base Case
if (root == null)
{
return null;
}
// Search for required condition
// in left and right half
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
// If the node is even
// and leaf node
if (root.data % 2 == 0
&& root.right==null
&& root.left==null)
return null;
return root;
}
let root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(8);
root.left.right = newNode(10);
root.right = newNode(7);
root.right.left = newNode(12);
root.right.right = newNode(5);
// Function Call
let newRoot = pruneTree(root);
// Print answer
printLevelOrder(newRoot);
// This code is contributed by decode2207.
</script>
Producción:
1 NULL 7 NULL 5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por yashbeersingh42 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA