Compruebe si el árbol binario dado tiene un subárbol con el mismo número de 1 y 0 | conjunto 2

Dado un árbol que tiene el valor de cada Node como 0 o 1 , la tarea es encontrar si el árbol binario dado contiene algún subárbol que tenga el mismo número de 0 y 1 , si se encuentra dicho subárbol, imprima Sí , de lo contrario, imprima No .
Ejemplos: 
 

Aporte: 
 

Salida: Sí 
Hay dos subárboles con el mismo número de 1 y 0. 
Por lo tanto, la salida es «Sí»
Entrada: 
 

Salida: Sí 
 

Acercarse: 
 

• Actualice todos los Nodes del árbol para que representen la suma de todos los Nodes del subárbol con raíz en el Node actual.
• Ahora bien, si existe algún Node cuyo valor es la mitad del número de Nodes en el árbol con raíz en el mismo Node, entonces es un subárbol válido.
• Si no existe tal Node, imprima No.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
// To store whether the tree contains a sub-tree
// with equal number of 0's and 1's
bool hasValidSubTree = false;
 
// Represents a node of the tree
struct node {
    int data;
    struct node *right, *left;
};
 
// To create a new node
struct node* newnode(int key)
{
    struct node* temp = new node;
    temp->data = key;
    temp->right = NULL;
    temp->left = NULL;
    return temp;
}
 
// Function to perform inorder traversal on
// the tree and print the nodes in that order
void inorder(struct node* root)
{
    if (root == NULL)
        return;
    inorder(root->left);
    cout << root->data << endl;
    inorder(root->right);
}
 
// Function to return the size of the
// sub-tree rooted at the current node
int size(struct node* root)
{
 
    int a = 0, b = 0;
 
    // If root is null or the valid sub-tree
    // has already been found
    if (root == NULL || hasValidSubTree)
        return 0;
 
    // Size of the right sub-tree
    a = size(root->right);
 
    // 1 is added for the parent
    a = a + 1;
 
    // Size of the left sub-tree
    b = size(root->left);
 
    // Total size of the tree
    // rooted at the current node
    a = b + a;
 
    // If the current tree has equal
    // number of 0's and 1's
    if (a % 2 == 0 && root->data == a / 2)
        hasValidSubTree = true;
 
    return a;
}
 
// Function to update and return the sum
// of all the tree nodes rooted at
// the passed node
int sum_tree(struct node* root)
{
    if (root == NULL)
        return 0;
 
    int a = 0, b = 0;
 
    // If left child exists
    if (root->left != NULL)
        a = sum_tree(root->left);
 
    // If right child exists
    if (root->right != NULL)
        b = sum_tree(root->right);
    root->data += (a + b);
 
    return root->data;
}
 
// Driver code
int main()
{
    struct node* root = newnode(1);
    root->right = newnode(0);
    root->right->right = newnode(1);
    root->right->right->right = newnode(1);
    root->left = newnode(0);
    root->left->left = newnode(1);
    root->left->left->left = newnode(1);
    root->left->right = newnode(0);
    root->left->right->left = newnode(1);
    root->left->right->left->left = newnode(1);
    root->left->right->right = newnode(0);
    root->left->right->right->left = newnode(1);
    root->left->right->right->left->left = newnode(1);
 
    sum_tree(root);
    size(root);
 
    if (hasValidSubTree)
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
import java.util.Comparator;
 
class GFG
{
 
 
// To store whether the tree contains a sub-tree
// with equal number of 0's and 1's
static boolean hasValidSubTree = false;
 
// Represents a node of the tree
static class node
{
    int data;
    node right, left;
};
 
// To create a new node
static node newnode(int key)
{
    node temp = new node();
    temp.data = key;
    temp.right = null;
    temp.left = null;
    return temp;
}
 
// Function to perform inorder traversal on
// the tree and print the nodes in that order
static void inorder( node root)
{
    if (root == null)
        return;
    inorder(root.left);
    System.out.print(root.data);
    inorder(root.right);
}
 
// Function to return the size of the
// sub-tree rooted at the current node
static int size( node root)
{
 
    int a = 0, b = 0;
 
    // If root is null or the valid sub-tree
    // has already been found
    if (root == null || hasValidSubTree)
        return 0;
 
    // Size of the right sub-tree
    a = size(root.right);
 
    // 1 is added for the parent
    a = a + 1;
 
    // Size of the left sub-tree
    b = size(root.left);
 
    // Total size of the tree
    // rooted at the current node
    a = b + a;
 
    // If the current tree has equal
    // number of 0's and 1's
    if (a % 2 == 0 && root.data == a / 2)
        hasValidSubTree = true;
 
    return a;
}
 
// Function to update and return the sum
// of all the tree nodes rooted at
// the passed node
static int sum_tree( node root)
{
    if (root == null)
        return 0;
 
    int a = 0, b = 0;
 
    // If left child exists
    if (root.left != null)
        a = sum_tree(root.left);
 
    // If right child exists
    if (root.right != null)
        b = sum_tree(root.right);
    root.data += (a + b);
 
    return root.data;
}
 
// Driver code
public static void main(String args[])
{
    node root = newnode(1);
    root.right = newnode(0);
    root.right.right = newnode(1);
    root.right.right.right = newnode(1);
    root.left = newnode(0);
    root.left.left = newnode(1);
    root.left.left.left = newnode(1);
    root.left.right = newnode(0);
    root.left.right.left = newnode(1);
    root.left.right.left.left = newnode(1);
    root.left.right.right = newnode(0);
    root.left.right.right.left = newnode(1);
    root.left.right.right.left.left = newnode(1);
 
    sum_tree(root);
    size(root);
 
    if (hasValidSubTree)
        System.out.print( "Yes");
    else
        System.out.print( "No");
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
class node:
     
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
 
# Function to perform inorder traversal on
# the tree and print the nodes in that order
def inorder(root):
 
    if root == None:
        return
         
    inorder(root.left)
    print(root.data)
    inorder(root.right)
 
# Function to return the size of the
# sub-tree rooted at the current node
def size(root):
 
    a, b = 0, 0
    global hasValidSubTree
 
    # If root is null or the valid
    # sub-tree has already been found
    if root == None or hasValidSubTree:
        return 0
 
    # Size of the right sub-tree
    a = size(root.right)
 
    # 1 is added for the parent
    a = a + 1
 
    # Size of the left sub-tree
    b = size(root.left)
 
    # Total size of the tree
    # rooted at the current node
    a = b + a
 
    # If the current tree has equal
    # number of 0's and 1's
    if a % 2 == 0 and root.data == a // 2:
        hasValidSubTree = True
 
    return a
 
# Function to update and return the sum
# of all the tree nodes rooted at
# the passed node
def sum_tree(root):
 
    if root == None:
        return 0
 
    a, b = 0, 0
 
    # If left child exists
    if root.left != None:
        a = sum_tree(root.left)
 
    # If right child exists
    if root.right != None:
        b = sum_tree(root.right)
     
    root.data += (a + b)
    return root.data
 
# Driver code
if __name__ == "__main__":
     
    # To store whether the tree contains a
    # sub-tree with equal number of 0's and 1's
    hasValidSubTree = False
 
    root = node(1)
    root.right = node(0)
    root.right.right = node(1)
    root.right.right.right = node(1)
    root.left = node(0)
    root.left.left = node(1)
    root.left.left.left = node(1)
    root.left.right = node(0)
    root.left.right.left = node(1)
    root.left.right.left.left = node(1)
    root.left.right.right = node(0)
    root.left.right.right.left = node(1)
    root.left.right.right.left.left = node(1)
 
    sum_tree(root)
    size(root)
 
    if hasValidSubTree:
        print("Yes")
    else:
        print("No")
 
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
 
class GFG
{
 
// To store whether the tree contains a sub-tree
// with equal number of 0's and 1's
static bool hasValidSubTree = false;
 
// Represents a node of the tree
public class node
{
    public int data;
    public node right, left;
};
 
// To create a new node
static node newnode(int key)
{
    node temp = new node();
    temp.data = key;
    temp.right = null;
    temp.left = null;
    return temp;
}
 
// Function to perform inorder traversal on
// the tree and print the nodes in that order
static void inorder( node root)
{
    if (root == null)
        return;
    inorder(root.left);
    Console.Write(root.data);
    inorder(root.right);
}
 
// Function to return the size of the
// sub-tree rooted at the current node
static int size( node root)
{
 
    int a = 0, b = 0;
 
    // If root is null or the valid sub-tree
    // has already been found
    if (root == null || hasValidSubTree)
        return 0;
 
    // Size of the right sub-tree
    a = size(root.right);
 
    // 1 is added for the parent
    a = a + 1;
 
    // Size of the left sub-tree
    b = size(root.left);
 
    // Total size of the tree
    // rooted at the current node
    a = b + a;
 
    // If the current tree has equal
    // number of 0's and 1's
    if (a % 2 == 0 && root.data == a / 2)
        hasValidSubTree = true;
 
    return a;
}
 
// Function to update and return the sum
// of all the tree nodes rooted at
// the passed node
static int sum_tree( node root)
{
    if (root == null)
        return 0;
 
    int a = 0, b = 0;
 
    // If left child exists
    if (root.left != null)
        a = sum_tree(root.left);
 
    // If right child exists
    if (root.right != null)
        b = sum_tree(root.right);
    root.data += (a + b);
 
    return root.data;
}
 
// Driver code
public static void Main(String []args)
{
    node root = newnode(1);
    root.right = newnode(0);
    root.right.right = newnode(1);
    root.right.right.right = newnode(1);
    root.left = newnode(0);
    root.left.left = newnode(1);
    root.left.left.left = newnode(1);
    root.left.right = newnode(0);
    root.left.right.left = newnode(1);
    root.left.right.left.left = newnode(1);
    root.left.right.right = newnode(0);
    root.left.right.right.left = newnode(1);
    root.left.right.right.left.left = newnode(1);
 
    sum_tree(root);
    size(root);
 
    if (hasValidSubTree)
        Console.Write( "Yes");
    else
        Console.Write( "No");
}
}
 
// This code contributed by Rajput-Ji

<script>
 
    // JavaScript implementation of the approach
     
    // To store whether the tree contains a sub-tree
    // with equal number of 0's and 1's
    let hasValidSubTree = false;
     
    // Binary tree node
    class node
    {
        constructor(key) {
           this.left = null;
           this.right = null;
           this.data = key;
        }
    }
     
    // To create a new node
    function newnode(key)
    {
        let temp = new node(key);
        return temp;
    }
 
    // Function to perform inorder traversal on
    // the tree and print the nodes in that order
    function inorder(root)
    {
        if (root == null)
            return;
        inorder(root.left);
        document.write(root.data);
        inorder(root.right);
    }
 
    // Function to return the size of the
    // sub-tree rooted at the current node
    function size(root)
    {
 
        let a = 0, b = 0;
 
        // If root is null or the valid sub-tree
        // has already been found
        if (root == null || hasValidSubTree)
            return 0;
 
        // Size of the right sub-tree
        a = size(root.right);
 
        // 1 is added for the parent
        a = a + 1;
 
        // Size of the left sub-tree
        b = size(root.left);
 
        // Total size of the tree
        // rooted at the current node
        a = b + a;
 
        // If the current tree has equal
        // number of 0's and 1's
        if (a % 2 == 0 && root.data == parseInt(a / 2, 10))
            hasValidSubTree = true;
 
        return a;
    }
 
    // Function to update and return the sum
    // of all the tree nodes rooted at
    // the passed node
    function sum_tree(root)
    {
        if (root == null)
            return 0;
 
        let a = 0, b = 0;
 
        // If left child exists
        if (root.left != null)
            a = sum_tree(root.left);
 
        // If right child exists
        if (root.right != null)
            b = sum_tree(root.right);
        root.data += (a + b);
 
        return root.data;
    }
     
    let root = newnode(1);
    root.right = newnode(0);
    root.right.right = newnode(1);
    root.right.right.right = newnode(1);
    root.left = newnode(0);
    root.left.left = newnode(1);
    root.left.left.left = newnode(1);
    root.left.right = newnode(0);
    root.left.right.left = newnode(1);
    root.left.right.left.left = newnode(1);
    root.left.right.right = newnode(0);
    root.left.right.right.left = newnode(1);
    root.left.right.right.left.left = newnode(1);
   
    sum_tree(root);
    size(root);
   
    if (hasValidSubTree)
        document.write( "Yes");
    else
        document.write( "No");
 
</script>

No