Dado un árbol binario , la tarea es recortar este árbol para cualquier subárbol que contenga solo 0.
Ejemplos:
Input:
1
\
0
/ \
0 1
Output:
1
\
0
\
1
Explanation:
The subtree shown as bold below
does not contain any 1.
Hence it can be trimmed.
1
\
0
/ \
0 1
Input:
1
/ \
1 0
/ \ / \
1 1 0 1
/
0
Output:
1
/ \
1 0
/ \ \
1 1 1
Input:
1
/ \
0 1
/ \ / \
0 0 0 1
Output:
1
\
1
\
1
Enfoque: el problema dado se puede resolver utilizando el recorrido posterior al pedido . La idea es devolver el Node nulo al padre si tanto el subárbol izquierdo como el derecho son nulos y el valor del Node actual es 0. Esto elimina los subárboles que no contienen ni un solo 1. Siga los pasos a continuación para resolver el problema:
- Si la raíz es nula, simplemente devolvemos nulo.
- Llame a la función recursivamente en los subárboles izquierdo y derecho
- Si el subárbol izquierdo y el subárbol derecho devuelven nulo y el valor del Node actual es 0, devuelven nulo
- De lo contrario, devuelve el Node actual en sí.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <iostream>
using namespace std;
class TreeNode {
public:
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val)
{
data = val;
left = NULL;
right = NULL;
}
};
// Inorder function to print the tree
void inorderPrint(TreeNode* root)
{
if (root == NULL)
return;
inorderPrint(root->left);
cout << root->data << " ";
inorderPrint(root->right);
}
// Postorder traversal
TreeNode* TrimTree(TreeNode* root)
{
if (!root)
return nullptr;
// Traverse from leaf to node
root->left = TrimTree(root->left);
root->right = TrimTree(root->right);
// We only trim if the node's value is 0
// and children are null
if (root->data == 0 && root->left == nullptr
&& root->right == nullptr) {
// We trim the subtree by returning nullptr
return nullptr;
}
// Otherwise we leave the node the way it is
return root;
}
// Driver code
int main()
{
/*
1
/ \
0 1
/ \ / \
0 0 0 1
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(0);
root->right = new TreeNode(1);
root->left->left = new TreeNode(0);
root->left->right = new TreeNode(0);
root->right->left = new TreeNode(0);
root->right->right = new TreeNode(1);
TreeNode* ReceivedRoot = TrimTree(root);
cout << endl;
inorderPrint(ReceivedRoot);
/*
1
\
1
\
1
*/
}
Java
// Java program for above approach
class GFG{
static class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int val)
{
data = val;
left = null;
right = null;
}
};
// Inorder function to print the tree
static void inorderPrint(TreeNode root)
{
if (root == null)
return;
inorderPrint(root.left);
System.out.print(root.data+ " ");
inorderPrint(root.right);
}
// Postorder traversal
static TreeNode TrimTree(TreeNode root)
{
if (root==null)
return null;
// Traverse from leaf to node
root.left = TrimTree(root.left);
root.right = TrimTree(root.right);
// We only trim if the node's value is 0
// and children are null
if (root.data == 0 && root.left == null
&& root.right == null) {
// We trim the subtree by returning null
return null;
}
// Otherwise we leave the node the way it is
return root;
}
// Driver code
public static void main(String[] args)
{
/*
1
/ \
0 1
/ \ / \
0 0 0 1
*/
TreeNode root = new TreeNode(1);
root.left = new TreeNode(0);
root.right = new TreeNode(1);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(0);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(1);
TreeNode ReceivedRoot = TrimTree(root);
System.out.println();
inorderPrint(ReceivedRoot);
/*
1
\
1
\
1
*/
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program for above approach class TreeNode: def __init__(self, data): self.data = data # Assign data self.left = None self.right = None; # Inorder function to print the tree def inorderPrint(root): if (root == None): return; inorderPrint(root.left); print(root.data, end = " "); inorderPrint(root.right); # Postorder traversal def TrimTree(root): if (root == None): return None; # Traverse from leaf to Node root.left = TrimTree(root.left); root.right = TrimTree(root.right); # We only trim if the Node's value is 0 # and children are None if (root.data == 0 and root.left == None and root.right == None): # We trim the subtree by returning None return None; # Otherwise we leave the Node the way it is return root; # Driver code if __name__ == '__main__': ''' 1 / \ 0 1 / \ / \ 0 0 0 1 ''' root = TreeNode(1); root.left = TreeNode(0); root.right = TreeNode(1); root.left.left = TreeNode(0); root.left.right = TreeNode(0); root.right.left = TreeNode(0); root.right.right = TreeNode(1); ReceivedRoot = TrimTree(root); print(); inorderPrint(ReceivedRoot); ''' 1 \ 1 \ 1 ''' # This code is contributed by shikhasingrajput
C#
// C# program for above approach
using System;
public class GFG{
class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int val)
{
data = val;
left = null;
right = null;
}
};
// Inorder function to print the tree
static void inorderPrint(TreeNode root)
{
if (root == null)
return;
inorderPrint(root.left);
Console.Write(root.data+ " ");
inorderPrint(root.right);
}
// Postorder traversal
static TreeNode TrimTree(TreeNode root)
{
if (root==null)
return null;
// Traverse from leaf to node
root.left = TrimTree(root.left);
root.right = TrimTree(root.right);
// We only trim if the node's value is 0
// and children are null
if (root.data == 0 && root.left == null
&& root.right == null) {
// We trim the subtree by returning null
return null;
}
// Otherwise we leave the node the way it is
return root;
}
// Driver code
public static void Main(String[] args)
{
/*
1
/ \
0 1
/ \ / \
0 0 0 1
*/
TreeNode root = new TreeNode(1);
root.left = new TreeNode(0);
root.right = new TreeNode(1);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(0);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(1);
TreeNode ReceivedRoot = TrimTree(root);
Console.WriteLine();
inorderPrint(ReceivedRoot);
/*
1
\
1
\
1
*/
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
class TreeNode {
constructor( val)
{
this.data = val;
this.left = null;
this.right = null;
}
};
// Inorder function to print the tree
function inorderPrint( root)
{
if (root == null)
return;
inorderPrint(root.left);
document.write(root.data + " ");
inorderPrint(root.right);
}
// Postorder traversal
function TrimTree( root)
{
if (!root)
return null;
// Traverse from leaf to node
root.left = TrimTree(root.left);
root.right = TrimTree(root.right);
// We only trim if the node's value is 0
// and children are null
if (root.data == 0 && root.left == null
&& root.right == null) {
// We trim the subtree by returning nullptr
return null;
}
// Otherwise we leave the node the way it is
return root;
}
// Driver code
/*
1
/ \
0 1
/ \ / \
0 0 0 1
*/
let root = new TreeNode(1);
root.left = new TreeNode(0);
root.right = new TreeNode(1);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(0);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(1);
let ReceivedRoot = TrimTree(root);
document.write('<br>')
inorderPrint(ReceivedRoot);
/*
1
\
1
\
1
*/
// This code is contributed by Potta Lokesh
</script>
Producción:
1 1 1
Complejidad temporal: O(N), donde N es el número de Nodes del árbol.
Espacio auxiliar: O(H), la pila de llamadas recursivas puede ser tan grande como la altura H del árbol. En el peor de los casos , H = N, cuando el árbol está sesgado.
Publicación traducida automáticamente
Artículo escrito por rishabhbatra53 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA