Dados dos árboles binarios, compruebe si el primer árbol es un subárbol del segundo. Un subárbol de un árbol T es un árbol S que consta de un Node en T y todos sus descendientes en T. El subárbol correspondiente al Node raíz es el árbol completo; el subárbol correspondiente a cualquier otro Node se denomina subárbol propio.
Ejemplos:
Entrada: Tree-T Tree-S
1 3
/ \ /
2 3 6
/ \ /
4 5 6
Salida: Sí
Explicación:
La altura de un Tree-S es -2
En el Tree-T los Nodes con altura 2 son -{2 ,3}
En los Nodes {2,3} los Nodes que satisfacen el subárbol idéntico con el árbol-S son {3}
Entonces, existe un subárbol idéntico, es decir, el árbol-S en el árbol-TEntrada: Árbol-T Árbol-S
26 10
/ \ / \
10 3 4 6
/ \ \ \
4 6 3 30
\
30
Enfoque ingenuo: El enfoque ingenuo se analiza en el Conjunto 1 de este problema.
Enfoque eficiente: el enfoque eficiente basado en la identificación única de un árbol a partir de su recorrido en orden y preorden/postorden se analiza en el Conjunto 2 de este problema.
Enfoque eficiente alternativo: el enfoque es encontrar todos los Nodes a la misma altura que la altura del Árbol-S en el Árbol-T y luego comparar.
- Calcule inicialmente la altura del subárbol dado ( Árbol -S ).
- En el siguiente paso, busque todos los Nodes del Árbol-T que tengan una altura como la altura del Árbol-S y almacene su dirección.
- Luego, desde cada Node, almacenamos, verificamos si ese es un subárbol idéntico o no.
- En este enfoque, no es necesario verificar para todos los Nodes si se trata de un subárbol idéntico o no, ya que tenemos la altura como parámetro en el que se debe realizar una validación de subárbol realmente idéntica.
A continuación se muestra la implementación de lo anterior.
C++
// C++ program to check if a binary tree
// Is subtree of another binary tree
#include <bits/stdc++.h>
using namespace std;
// Structure of a Binary Tree Node
struct Node {
int data;
struct Node *left, *right;
};
// Utility function to
// Create a new tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Function to calculate
// The height of the tree
int height_of_tree(Node* root)
{
if (!root)
return 0;
// Calculate the left subtree
// And right subtree height
int left = height_of_tree(root->left);
int right = height_of_tree(root->right);
return 1 + max(left, right);
}
// Function to check
// It is a subtree or not
bool CheckSubTree(Node* T, Node* S)
{
if (S == NULL && T == NULL)
return true;
if (T == NULL || S == NULL)
return false;
if (T->data != S->data)
return false;
return CheckSubTree(T->left, S->left)
&& CheckSubTree(T->right, S->right);
}
// Function to extract the
// nodes of height of the subtree
// i.e tree-S from the parent
// tree(T-tree) using the height of the tree
int subtree_height(Node* root,
vector<Node*>& nodes,
int h)
{
if (root == NULL)
return 0;
else {
// Calculating the height
// Of the tree at each node
int left = subtree_height(root->left,
nodes, h);
int right = subtree_height(root->right,
nodes, h);
int height = max(left, right) + 1;
// If height equals to height
// of the subtree then store it
if (height == h)
nodes.push_back(root);
return height;
}
}
// Function to check if it is a subtree
bool isSubTree(Node* T, Node* S)
{
if (T == NULL && S == NULL)
return true;
if (T == NULL || S == NULL)
return false;
// Calling the height_of_tree
// Function to calculate
// The height of subtree-S
int h = height_of_tree(S);
vector<Node*> nodes;
// Calling the subtree_height
// To extract all the nodes
// Of height of subtree(S) i.e height-h
int h1 = subtree_height(T, nodes, h);
bool result = false;
int n = nodes.size();
for (int i = 0; i < n; i++) {
// If the data of the
// node of tree-T at height-h
// is equal to the data
// of root of subtree-S
// then check if is a subtree
// of the parent tree or not
if (nodes[i]->data == S->data)
result = CheckSubTree(nodes[i], S);
// If any node is satisfying
// the CheckSubTree then return true
if (result)
return true;
}
// If no node is satisfying
// the subtree the return false
return false;
}
// Driver program
int main()
{
// Create binary tree T in above diagram
Node* T = newNode(1);
T->left = newNode(2);
T->right = newNode(3);
T->left->left = newNode(4);
T->left->right = newNode(5);
T->right->left = newNode(6);
// Create binary tree S shown in diagram
Node* S = newNode(3);
S->left = newNode(6);
// Lets us call the function
// isSubTree() which checks
// that the given Tree -S is a subtree
// of tree -T(parent tree)
if (isSubTree(T, S))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java program to check if a binary tree
// Is subtree of another binary tree
import java.util.*;
class GFG{
// Structure of a Binary Tree Node
static class Node {
int data;
Node left, right;
};
static Vector<Node> nodes = new Vector<Node>();
// Utility function to
// Create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to calculate
// The height of the tree
static int height_of_tree(Node root)
{
if (root == null)
return 0;
// Calculate the left subtree
// And right subtree height
int left = height_of_tree(root.left);
int right = height_of_tree(root.right);
return 1 + Math.max(left, right);
}
// Function to check
// It is a subtree or not
static boolean CheckSubTree(Node T, Node S)
{
if (S == null && T == null)
return true;
if (T == null || S == null)
return false;
if (T.data != S.data)
return false;
return CheckSubTree(T.left, S.left)
&& CheckSubTree(T.right, S.right);
}
// Function to extract the
// nodes of height of the subtree
// i.e tree-S from the parent
// tree(T-tree) using the height of the tree
static int subtree_height(Node root,
int h)
{
if (root == null)
return 0;
else {
// Calculating the height
// Of the tree at each node
int left = subtree_height(root.left, h);
int right = subtree_height(root.right, h);
int height = Math.max(left, right) + 1;
// If height equals to height
// of the subtree then store it
if (height == h)
nodes.add(root);
return height;
}
}
// Function to check if it is a subtree
static boolean isSubTree(Node T, Node S)
{
if (T == null && S == null)
return true;
if (T == null || S == null)
return false;
// Calling the height_of_tree
// Function to calculate
// The height of subtree-S
int h = height_of_tree(S);
// Calling the subtree_height
// To extract all the nodes
// Of height of subtree(S) i.e height-h
int h1 = subtree_height(T, h);
boolean result = false;
int n = nodes.size();
for (int i = 0; i < n; i++) {
// If the data of the
// node of tree-T at height-h
// is equal to the data
// of root of subtree-S
// then check if is a subtree
// of the parent tree or not
if (nodes.get(i).data == S.data)
result = CheckSubTree(nodes.get(i), S);
// If any node is satisfying
// the CheckSubTree then return true
if (result)
return true;
}
// If no node is satisfying
// the subtree the return false
return false;
}
// Driver program
public static void main(String[] args)
{
// Create binary tree T in above diagram
Node T = newNode(1);
T.left = newNode(2);
T.right = newNode(3);
T.left.left = newNode(4);
T.left.right = newNode(5);
T.right.left = newNode(6);
// Create binary tree S shown in diagram
Node S = newNode(3);
S.left = newNode(6);
// Lets us call the function
// isSubTree() which checks
// that the given Tree -S is a subtree
// of tree -T(parent tree)
if (isSubTree(T, S))
System.out.print("Yes" +"\n");
else
System.out.print("No" +"\n");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program to check if a binary tree
# Is subtree of another binary tree
# Structure of a Binary Tree Node
from platform import node
class Node:
def __init__(self,data):
self.data = data
self.left = self.right = None
# Utility function to
# Create a new tree node
def newNode(data):
temp = Node(data)
return temp
# Function to calculate
# The height of the tree
def height_of_tree(root):
if (root == None):
return 0
# Calculate the left subtree
# And right subtree height
left = height_of_tree(root.left)
right = height_of_tree(root.right)
return 1 + max(left, right)
# Function to check
# It is a subtree or not
def CheckSubTree(T, S):
if (S == None and T == None):
return True
if (T == None or S == None):
return False
if (T.data != S.data):
return False
return CheckSubTree(T.left, S.left) and CheckSubTree(T.right, S.right)
# Function to extract the
# nodes of height of the subtree
# i.e tree-S from the parent
# tree(T-tree) using the height of the tree
def subtree_height(root,nodes,h):
if (root == None):
return 0
else:
# Calculating the height
# Of the tree at each node
left = subtree_height(root.left,nodes, h)
right = subtree_height(root.right, nodes, h)
height = max(left, right) + 1
# If height equals to height
# of the subtree then store it
if (height == h):
nodes.append(root)
return height
# Function to check if it is a subtree
def isSubTree(T, S):
if (T == None and S == None):
return True
if (T == None or S == None):
return False
# Calling the height_of_tree
# Function to calculate
# The height of subtree-S
h = height_of_tree(S)
nodes = []
# Calling the subtree_height
# To extract all the nodes
# Of height of subtree(S) i.e height-h
h1 = subtree_height(T, nodes, h)
result = False
n = len(nodes)
for i in range(n):
# If the data of the
# node of tree-T at height-h
# is equal to the data
# of root of subtree-S
# then check if is a subtree
# of the parent tree or not
if (nodes[i].data == S.data):
result = CheckSubTree(nodes[i], S)
# If any node is satisfying
# the CheckSubTree then return true
if (result):
return True
# If no node is satisfying
# the subtree the return false
return False
# Driver program
# Create binary tree T in above diagram
T = newNode(1)
T.left = newNode(2)
T.right = newNode(3)
T.left.left = newNode(4)
T.left.right = newNode(5)
T.right.left = newNode(6)
# Create binary tree S shown in diagram
S = newNode(3)
S.left = newNode(6)
# Lets us call the function
# isSubTree() which checks
# that the given Tree -S is a subtree
# of tree -T(parent tree)
if (isSubTree(T, S)):
print("Yes")
else:
print("No")
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program to check if a binary tree
// Is subtree of another binary tree
// Structure of a Binary Tree Node
class Node {
constructor(data){
this.data = data;
this.left = this.right = null;
}
};
// Utility function to
// Create a new tree node
function newNode(data)
{
let temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to calculate
// The height of the tree
function height_of_tree(root)
{
if (!root)
return 0;
// Calculate the left subtree
// And right subtree height
let left = height_of_tree(root.left);
let right = height_of_tree(root.right);
return 1 + Math.max(left, right);
}
// Function to check
// It is a subtree or not
function CheckSubTree(T, S)
{
if (S == null && T == null)
return true;
if (T == null || S == null)
return false;
if (T.data != S.data)
return false;
return CheckSubTree(T.left, S.left)
&& CheckSubTree(T.right, S.right);
}
// Function to extract the
// nodes of height of the subtree
// i.e tree-S from the parent
// tree(T-tree) using the height of the tree
function subtree_height(root,nodes,h)
{
if (root == null)
return 0;
else {
// Calculating the height
// Of the tree at each node
let left = subtree_height(root.left,
nodes, h);
let right = subtree_height(root.right,
nodes, h);
let height = Math.max(left, right) + 1;
// If height equals to height
// of the subtree then store it
if (height == h)
nodes.push(root);
return height;
}
}
// Function to check if it is a subtree
function isSubTree(T, S)
{
if (T == null && S == null)
return true;
if (T == null || S == null)
return false;
// Calling the height_of_tree
// Function to calculate
// The height of subtree-S
let h = height_of_tree(S);
let nodes = [];
// Calling the subtree_height
// To extract all the nodes
// Of height of subtree(S) i.e height-h
let h1 = subtree_height(T, nodes, h);
let result = false;
let n = nodes.length;
for (let i = 0; i < n; i++) {
// If the data of the
// node of tree-T at height-h
// is equal to the data
// of root of subtree-S
// then check if is a subtree
// of the parent tree or not
if (nodes[i].data == S.data)
result = CheckSubTree(nodes[i], S);
// If any node is satisfying
// the CheckSubTree then return true
if (result)
return true;
}
// If no node is satisfying
// the subtree the return false
return false;
}
// Driver program
// Create binary tree T in above diagram
let T = newNode(1);
T.left = newNode(2);
T.right = newNode(3);
T.left.left = newNode(4);
T.left.right = newNode(5);
T.right.left = newNode(6);
// Create binary tree S shown in diagram
let S = newNode(3);
S.left = newNode(6);
// Lets us call the function
// isSubTree() which checks
// that the given Tree -S is a subtree
// of tree -T(parent tree)
if (isSubTree(T, S))
document.write("Yes");
else
document.write("No");
// This code is contributed by shinjanpatra
</script>
Producción
Yes
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O( 2 H ) donde H es la altura del Árbol-T
Publicación traducida automáticamente
Artículo escrito por golirahul21 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA