Pregunta: Dado un árbol binario, averigüe si el árbol se puede plegar o no.
Un árbol se puede plegar si los subárboles izquierdo y derecho del árbol son una imagen especular de la estructura del otro. Un árbol vacío se considera plegable.
Consider the below trees:
(a) and (b) can be folded.
(c) and (d) cannot be folded.
(a)
10
/ \
7 15
\ /
9 11
(b)
10
/ \
7 15
/ \
9 11
(c)
10
/ \
7 15
/ /
5 11
(d)
10
/ \
7 15
/ \ /
9 10 12
Método 1 (Cambiar el subárbol izquierdo a su espejo y compararlo con el subárbol derecho)
Algoritmo: isFoldable(root)
C++
// C++ program to check foldable binary tree
#include <bits/stdc++.h>
using namespace std;
/* You would want to remove below
3 lines if your compiler supports
bool, true and false */
#define bool int
#define true 1
#define false 0
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
class node {
public:
int data;
node* left;
node* right;
};
/* converts a tree to its mirror image */
void mirror(node* node);
/* returns true if structure of
two trees a and b is same only
structure is considered for comparison, not data! */
bool isStructSame(node* a, node* b);
/* Returns true if the given tree is foldable */
bool isFoldable(node* root)
{
bool res;
/* base case */
if (root == NULL)
return true;
/* convert left subtree to its mirror */
mirror(root->left);
/* Compare the structures of the
right subtree and mirrored
left subtree */
res = isStructSame(root->left, root->right);
/* Get the original tree back */
mirror(root->left);
return res;
}
bool isStructSame(node* a, node* b)
{
if (a == NULL && b == NULL) {
return true;
}
if (a != NULL && b != NULL && isStructSame(a->left, b->left) && isStructSame(a->right, b->right)) {
return true;
}
return false;
}
/* UTILITY FUNCTIONS */
/* Change a tree so that the roles of the left and
right pointers are swapped at every node.
See https:// www.geeksforgeeks.org/?p=662 for details */
void mirror(node* Node)
{
if (Node == NULL)
return;
else {
node* temp;
/* do the subtrees */
mirror(Node->left);
mirror(Node->right);
/* swap the pointers in this node */
temp = Node->left;
Node->left = Node->right;
Node->right = temp;
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
/* Driver program to test mirror() */
int main(void)
{
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(5);
if (isFoldable(root) == 1) {
cout << "tree is foldable";
}
else {
cout << "\ntree is not foldable";
}
return 0;
}
// This code is contributed by rathbhupendra
C
#include <stdio.h>
#include <stdlib.h>
/* You would want to remove below 3 lines if your compiler
supports bool, true and false */
#define bool int
#define true 1
#define false 0
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};
/* converts a tree to its mirror image */
void mirror(struct node* node);
/* returns true if structure of two trees a and b is same
Only structure is considered for comparison, not data! */
bool isStructSame(struct node* a, struct node* b);
/* Returns true if the given tree is foldable */
bool isFoldable(struct node* root)
{
bool res;
/* base case */
if (root == NULL)
return true;
/* convert left subtree to its mirror */
mirror(root->left);
/* Compare the structures of the right subtree and mirrored
left subtree */
res = isStructSame(root->left, root->right);
/* Get the original tree back */
mirror(root->left);
return res;
}
bool isStructSame(struct node* a, struct node* b)
{
if (a == NULL && b == NULL) {
return true;
}
if (a != NULL && b != NULL && isStructSame(a->left, b->left) && isStructSame(a->right, b->right)) {
return true;
}
return false;
}
/* UTILITY FUNCTIONS */
/* Change a tree so that the roles of the left and
right pointers are swapped at every node.
See https:// www.geeksforgeeks.org/?p=662 for details */
void mirror(struct node* node)
{
if (node == NULL)
return;
else {
struct node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver program to test mirror() */
int main(void)
{
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(4);
root->left->right = newNode(5);
if (isFoldable(root) == 1) {
printf("\n tree is foldable");
}
else {
printf("\n tree is not foldable");
}
getchar();
return 0;
}
Java
// Java program to check foldable binary tree
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node {
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
/* Returns true if the given tree is foldable */
boolean isFoldable(Node node)
{
boolean res;
/* base case */
if (node == null)
return true;
/* convert left subtree to its mirror */
mirror(node.left);
/* Compare the structures of the right subtree and mirrored
left subtree */
res = isStructSame(node.left, node.right);
/* Get the original tree back */
mirror(node.left);
return res;
}
boolean isStructSame(Node a, Node b)
{
if (a == null && b == null)
return true;
if (a != null && b != null
&& isStructSame(a.left, b.left)
&& isStructSame(a.right, b.right))
return true;
return false;
}
/* UTILITY FUNCTIONS */
/* Change a tree so that the roles of the left and
right pointers are swapped at every node.
See https:// www.geeksforgeeks.org/?p=662 for details */
void mirror(Node node)
{
if (node == null)
return;
else {
Node temp;
/* do the subtrees */
mirror(node.left);
mirror(node.right);
/* swap the pointers in this node */
temp = node.left;
node.left = node.right;
node.right = temp;
}
}
/* Driver program to test above functions */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.right.left = new Node(4);
tree.root.left.right = new Node(5);
if (tree.isFoldable(tree.root))
System.out.println("tree is foldable");
else
System.out.println("Tree is not foldable");
}
}
// This code has been contributed by Mayank Jaiswal
C#
// C# program to check foldable
// binary tree
using System;
/* A binary tree node has data,
pointer to left child and
a pointer to right child */
class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
/* Returns true if the given
tree is foldable */
Boolean isFoldable(Node node)
{
Boolean res;
/* base case */
if (node == null)
return true;
/* convert left subtree
to its mirror */
mirror(node.left);
/* Compare the structures of the
right subtree and mirrored
left subtree */
res = isStructSame(node.left, node.right);
/* Get the original tree back */
mirror(node.left);
return res;
}
Boolean isStructSame(Node a, Node b)
{
if (a == null && b == null)
return true;
if (a != null && b != null && isStructSame(a.left, b.left) && isStructSame(a.right, b.right))
return true;
return false;
}
/* UTILITY FUNCTIONS */
/* Change a tree so that the roles
of the left and right pointers are
swapped at every node.
See https:// www.geeksforgeeks.org/?p=662
for details */
void mirror(Node node)
{
if (node == null)
return;
else {
Node temp;
/* do the subtrees */
mirror(node.left);
mirror(node.right);
/* swap the pointers in this node */
temp = node.left;
node.left = node.right;
node.right = temp;
}
}
// Driver Code
static public void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.right.left = new Node(4);
tree.root.left.right = new Node(5);
if (tree.isFoldable(tree.root))
Console.WriteLine("tree is foldable");
else
Console.WriteLine("Tree is not foldable");
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
class Node
{
constructor(item)
{
this.data=item;
this.left=this.right=null;
}
}
function isFoldable(node)
{
let res;
/* base case */
if (node == null)
return true;
/* convert left subtree to its mirror */
mirror(node.left);
/* Compare the structures of the right subtree and mirrored
left subtree */
res = isStructSame(node.left, node.right);
/* Get the original tree back */
mirror(node.left);
return res;
}
function isStructSame(a,b)
{
if (a == null && b == null)
return true;
if (a != null && b != null
&& isStructSame(a.left, b.left)
&& isStructSame(a.right, b.right))
return true;
return false;
}
function mirror(node)
{
if (node == null)
return;
else {
let temp;
/* do the subtrees */
mirror(node.left);
mirror(node.right);
/* swap the pointers in this node */
temp = node.left;
node.left = node.right;
node.right = temp;
}
}
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);
root.left.right = new Node(5);
if (isFoldable(root))
document.write("tree is foldable");
else
document.write("Tree is not foldable");
// This code is contributed by avanitrachhadiya2155
</script>
Python3
# Python3 program to check foldable binary tree
# A binary tree node has data,
# pointer to left child and a
# pointer to right child
class newNode:
def __init__(self, d):
self.data = d
self.left = None
self.right = None
# Returns true if the given
# tree is foldable
def isFoldable(node) :
# base case
if node == None :
return true
# convert left subtree to its mirror
mirror(node.left)
# Compare the structures of the right subtree and mirrored
#left subtree
res = isStructSame(node.left, node.right)
# Get the original tree back
mirror(node.left)
return res
def isStructSame(a,b) :
if a == None and b == None :
return True
if a != None and b != None and isStructSame(a.left, b.left) and isStructSame(a.right, b.right) :
return True
return False
def mirror(node) :
if node == None :
return
else :
# do the subtrees
mirror(node.left)
mirror(node.right)
# swap the pointers in this node
temp = node.left
node.left = node.right
node.right = temp
# Driver Code
if __name__ == '__main__':
'''
The constructed binary tree is
1
/ \
2 3
\ /
4 5
'''
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.right.left = newNode(4)
root.left.right = newNode(5)
if isFoldable(root) :
print("tree is foldable")
else :
print("Tree is not foldable")
C++
#include <bits/stdc++.h>
using namespace std;
/* You would want to remove below 3 lines if your compiler
supports bool, true and false */
#define bool int
#define true 1
#define false 0
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
int data;
node* left;
node* right;
};
/* A utility function that checks
if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldableUtil(node* n1, node* n2);
/* Returns true if the given tree can be folded */
bool IsFoldable(node* root)
{
if (root == NULL) {
return true;
}
return IsFoldableUtil(root->left, root->right);
}
/* A utility function that checks
if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldableUtil(node* n1, node* n2)
{
/* If both left and right subtrees are NULL,
then return true */
if (n1 == NULL && n2 == NULL) {
return true;
}
/* If one of the trees is NULL and other is not,
then return false */
if (n1 == NULL || n2 == NULL) {
return false;
}
/* Otherwise check if left and right subtrees are
mirrors of their counterparts */
return IsFoldableUtil(n1->left, n2->right)
&& IsFoldableUtil(n1->right, n2->left);
}
/*UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
/* Driver code */
int main(void)
{
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(5);
if (IsFoldable(root) == true) {
cout << "Tree is foldable";
}
else {
cout << "Tree is not foldable";
}
return 0;
}
// This is code is contributed by rathbhupendra
C
#include <stdio.h>
#include <stdlib.h>
/* You would want to remove below 3 lines if your compiler
supports bool, true and false */
#define bool int
#define true 1
#define false 0
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};
/* A utility function that checks if trees with roots as n1
and n2 are mirror of each other */
bool IsFoldableUtil(struct node* n1, struct node* n2);
/* Returns true if the given tree can be folded */
bool IsFoldable(struct node* root)
{
if (root == NULL) {
return true;
}
return IsFoldableUtil(root->left, root->right);
}
/* A utility function that checks if trees with roots as n1
and n2 are mirror of each other */
bool IsFoldableUtil(struct node* n1, struct node* n2)
{
/* If both left and right subtrees are NULL,
then return true */
if (n1 == NULL && n2 == NULL) {
return true;
}
/* If one of the trees is NULL and other is not,
then return false */
if (n1 == NULL || n2 == NULL) {
return false;
}
/* Otherwise check if left and right subtrees are
mirrors of their counterparts */
return IsFoldableUtil(n1->left, n2->right)
&& IsFoldableUtil(n1->right, n2->left);
}
/*UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver program to test mirror() */
int main(void)
{
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(5);
if (IsFoldable(root) == true) {
printf("\n tree is foldable");
}
else {
printf("\n tree is not foldable");
}
getchar();
return 0;
}
Java
// Java program to check foldable binary tree
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node {
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
/* Returns true if the given tree can be folded */
boolean IsFoldable(Node node)
{
if (node == null)
return true;
return IsFoldableUtil(node.left, node.right);
}
/* A utility function that checks if trees with roots as
n1 and n2 are mirror of each other */
boolean IsFoldableUtil(Node n1, Node n2)
{
/* If both left and right subtrees are NULL,
then return true */
if (n1 == null && n2 == null)
return true;
/* If one of the trees is NULL and other is not,
then return false */
if (n1 == null || n2 == null)
return false;
/* Otherwise check if left and right subtrees are
mirrors of their counterparts */
return IsFoldableUtil(n1.left, n2.right)
&& IsFoldableUtil(n1.right, n2.left);
}
/* Driver program to test above functions */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.right.left = new Node(4);
tree.root.left.right = new Node(5);
if (tree.IsFoldable(tree.root))
System.out.println("tree is foldable");
else
System.out.println("Tree is not foldable");
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python3 program to check
# foldable binary tree
# Utility function to create a new
# tree node
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Returns true if the given tree can be folded
def IsFoldable(root):
if (root == None):
return True
return IsFoldableUtil(root.left, root.right)
# A utility function that checks
# if trees with roots as n1 and n2
# are mirror of each other
def IsFoldableUtil(n1, n2):
# If both left and right subtrees are NULL,
# then return true
if n1 == None and n2 == None:
return True
# If one of the trees is NULL and other is not,
# then return false
if n1 == None or n2 == None:
return False
# Otherwise check if left and
# right subtrees are mirrors of
# their counterparts
d1 = IsFoldableUtil(n1.left, n2.right)
d2 = IsFoldableUtil(n1.right, n2.left)
return d1 and d2
# Driver code
if __name__ == "__main__":
""" The constructed binary tree is
1
/ \
2 3
\ /
4 5
"""
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.right = newNode(4)
root.right.left = newNode(5)
if IsFoldable(root):
print("Tree is foldable")
else:
print("Tree is not foldable")
# This code is contributed by
# Anupam Baranwal(anupambaranwal)
C#
// C# program to check foldable binary tree
using System;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree {
Node root;
/* Returns true if the given tree can be folded */
bool IsFoldable(Node node)
{
if (node == null)
return true;
return IsFoldableUtil(node.left, node.right);
}
/* A utility function that checks if
trees with roots as n1 and n2
are mirror of each other */
bool IsFoldableUtil(Node n1, Node n2)
{
/* If both left and right subtrees are NULL,
then return true */
if (n1 == null && n2 == null)
return true;
/* If one of the trees is NULL and other is not,
then return false */
if (n1 == null || n2 == null)
return false;
/* Otherwise check if left and right subtrees are
mirrors of their counterparts */
return IsFoldableUtil(n1.left, n2.right)
&& IsFoldableUtil(n1.right, n2.left);
}
/* Driver code */
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.right.left = new Node(4);
tree.root.left.right = new Node(5);
if (tree.IsFoldable(tree.root))
Console.WriteLine("tree is foldable");
else
Console.WriteLine("Tree is not foldable");
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program to check foldable binary tree
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
let root;
/* Returns true if the given tree can be folded */
function IsFoldable(node)
{
if (node == null)
return true;
return IsFoldableUtil(node.left, node.right);
}
/* A utility function that checks if trees with roots as
n1 and n2 are mirror of each other */
function IsFoldableUtil(n1, n2)
{
/* If both left and right subtrees are NULL,
then return true */
if (n1 == null && n2 == null)
return true;
/* If one of the trees is NULL and other is not,
then return false */
if (n1 == null || n2 == null)
return false;
/* Otherwise check if left and right subtrees are
mirrors of their counterparts */
return IsFoldableUtil(n1.left, n2.right)
&& IsFoldableUtil(n1.right, n2.left);
}
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);
root.left.right = new Node(5);
if (IsFoldable(root))
document.write("tree is foldable");
else
document.write("Tree is not foldable");
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA