Suma de Nodes que tienen suma de subárboles de paridades opuestas

Posted on by Rudeus Greyrat

Dado un árbol binario , la tarea es encontrar la suma de todos esos Nodes del árbol dado cuya suma del subárbol izquierdo y derecho es impar y par o par e impar respectivamente.

Ejemplos:

Entrada:
                 11
             / \
          23 44
        / \ / \
      13 9 22 7
                 / \
               6 15
Salida: 33
Explicación: Solo hay dos Nodes de este tipo: 

  • El Node 22 tiene un subárbol izquierdo y un subárbol derecho que suman 6 (par) y 15 (impar).
  • El Node 11 tiene un subárbol izquierdo y un subárbol derecho que suman 45 (impar) y 94 (par).

Por lo tanto, la suma total = 22 + 11 = 33.

Entrada:
               11
             /     
           5       
        / \      
      3 1  
Salida: 0
Explicación: No existe tal Node que satisfaga la condición dada.

Enfoque: la idea es calcular recursivamente la suma del subárbol izquierdo y la suma del subárbol derecho y luego verificar la condición dada. Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable ans como 0 para almacenar la suma de todos esos Nodes.
  • Realice el PostOrder Traversal en el Tree dado .
  • Encuentre la suma del subárbol izquierdo y derecho para cada Node y verifique si la suma no es cero y verifique si la suma de ambas sumas es impar o no. Si se determina que es cierto, incluya el valor del Node actual en ans .
  • Devuelve la suma de todos los Nodes del subárbol izquierdo, el subárbol derecho y el valor del Node actual en cada llamada recursiva.
  • Después de completar los pasos anteriores, imprima el valor de ans como resultado.

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;
 
// A binary tree node
struct Node {
 
    int data;
    Node *left, *right;   
};
 
/* 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 = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return(node);
}
    // Stores the desired result
     int mSum;
 
    // Function to find the sum of nodes
    // with subtree sums of opposite parities
     int getSum(Node *root)
    {
        
        // Return 0, if node is NULL
        if (root == NULL)
            return 0;
 
        // Recursively call left and
        // right subtree
        int lSum = getSum(root->left);
        int rSum = getSum(root->right);
 
        // Update mSum, if one subtree
        // sum is even and another is odd
        if (lSum != 0 && rSum != 0)
            if ((lSum + rSum) % 2 != 0)
                mSum += root->data;
 
        // Return the sum of subtree
        return lSum + rSum + root->data;
    }
 
    // Driver Code
    int main()
    {
        // Given number of nodes
        int n = 9;
 
        // Binary tree formation
       struct Node *root = newNode(11);
        root->left =  newNode(23);
        root->right =  newNode(44);
        root->left->left =  newNode(13);
        root->left->right =  newNode(9);
        root->right->left =  newNode(22);
        root->right->right =  newNode(7);
        root->right->left->left =  newNode(6);
        root->right->left->right = newNode(15);
 
        // 11
        //    /     \
        // 23       44
        //  /  \     /   \
        // 13   9   22     7
        //         / \
        // 6   15
 
        mSum = 0;
        getSum(root);
 
        // Print the sum
        cout<<(mSum);
    }
 
// This code is contributed by 29AjayKumar

Java

// Java program for the above approach
 
import java.util.*;
import java.lang.*;
 
// A binary tree node
class Node {
 
    int data;
    Node left, right;
 
    // Constructor
    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
// Binary Tree Class
class BinaryTree {
 
    // Stores the desired result
    static int mSum;
 
    Node root;
 
    // Function to find the sum of nodes
    // with subtree sums of opposite parities
    static int getSum(Node root)
    {
        // Return 0, if node is null
        if (root == null)
            return 0;
 
        // Recursively call left and
        // right subtree
        int lSum = getSum(root.left);
        int rSum = getSum(root.right);
 
        // Update mSum, if one subtree
        // sum is even and another is odd
        if (lSum != 0 && rSum != 0)
            if ((lSum + rSum) % 2 != 0)
                mSum += root.data;
 
        // Return the sum of subtree
        return lSum + rSum + root.data;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given number of nodes
        int n = 9;
 
        BinaryTree tree = new BinaryTree();
 
        // Binary tree formation
        tree.root = new Node(11);
        tree.root.left = new Node(23);
        tree.root.right = new Node(44);
        tree.root.left.left = new Node(13);
        tree.root.left.right = new Node(9);
        tree.root.right.left = new Node(22);
        tree.root.right.right = new Node(7);
        tree.root.right.left.left = new Node(6);
        tree.root.right.left.right = new Node(15);
 
        // 11
        //    /     \
        // 23       44
        //  /  \     /   \
        // 13   9   22     7
        //         / \
        // 6   15
 
        mSum = 0;
 
        getSum(tree.root);
 
        // Print the sum
        System.out.println(mSum);
    }
}

Python3

# Python3 program for the above approach
 
# A binary tree node
class Node:
     
    def __init__(self, x):
         
        self.data = x
        self.left = None
        self.right = None
 
# Stores the desired result
mSum = 0
 
# Function to find the sum of nodes
# with subtree sums of opposite parities
def getSum(root):
     
    global mSum
     
    # Return 0, if node is None
    if (root == None):
        return 0
 
    # Recursively call left and
    # right subtree
    lSum = getSum(root.left)
    rSum = getSum(root.right)
 
    # Update mSum, if one subtree
    # sum is even and another is odd
    if (lSum != 0 and rSum != 0):
        if ((lSum + rSum) % 2 != 0):
            mSum += root.data
 
    # Return the sum of subtree
    return lSum + rSum + root.data
 
# Driver Code
if __name__ == '__main__':
     
    # Given number of nodes
    n = 9
 
    # Binary tree formation
    root = Node(11)
    root.left = Node(23)
    root.right = Node(44)
    root.left.left = Node(13)
    root.left.right = Node(9)
    root.right.left = Node(22)
    root.right.right = Node(7)
    root.right.left.left = Node(6)
    root.right.left.right = Node(15)
 
    #     11
    #   /     \
    #  23       44
    # /  \     /   \
    #13   9   22     7
    #        / \
    #       6   15
 
    mSum = 0
 
    getSum(root)
 
    # Print the sum
    print(mSum)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
// A binary tree node
public class Node
{
    public int data;
    public Node left, right;
     
    // Constructor
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
// Binary Tree Class
class BinaryTree{
 
// Stores the desired result
static int mSum;
 
Node root;
 
// Function to find the sum of nodes
// with subtree sums of opposite parities
static int getSum(Node root)
{
     
    // Return 0, if node is null
    if (root == null)
        return 0;
 
    // Recursively call left and
    // right subtree
    int lSum = getSum(root.left);
    int rSum = getSum(root.right);
 
    // Update mSum, if one subtree
    // sum is even and another is odd
    if (lSum != 0 && rSum != 0)
        if ((lSum + rSum) % 2 != 0)
            mSum += root.data;
 
    // Return the sum of subtree
    return lSum + rSum + root.data;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given number of nodes
    //int n = 9;
 
    BinaryTree tree = new BinaryTree();
 
    // Binary tree formation
    tree.root = new Node(11);
    tree.root.left = new Node(23);
    tree.root.right = new Node(44);
    tree.root.left.left = new Node(13);
    tree.root.left.right = new Node(9);
    tree.root.right.left = new Node(22);
    tree.root.right.right = new Node(7);
    tree.root.right.left.left = new Node(6);
    tree.root.right.left.right = new Node(15);
 
    //       11
    //    /     \
    //   23       44
    //  /  \     /   \
    // 13   9   22     7
    //         / \
    //        6   15
    mSum = 0;
 
    getSum(tree.root);
 
    // Print the sum
    Console.WriteLine(mSum);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program for the above approach
 
// A binary tree node
class Node
{
    constructor(item)
    {
        this.left = null;
        this.right = null;
        this.data = item;
    }
}
 
// Stores the desired result
let mSum;
 
let root;
 
class BinaryTree
{
    constructor()
    {
        this.root = null;
    }
}
 
// Function to find the sum of nodes
// with subtree sums of opposite parities
function getSum(root)
{
     
    // Return 0, if node is null
    if (root == null)
        return 0;
 
    // Recursively call left and
    // right subtree
    let lSum = getSum(root.left);
    let rSum = getSum(root.right);
 
    // Update mSum, if one subtree
    // sum is even and another is odd
    if (lSum != 0 && rSum != 0)
        if ((lSum + rSum) % 2 != 0)
            mSum += root.data;
 
    // Return the sum of subtree
    return lSum + rSum + root.data;
}
 
// Driver code
 
// Given number of nodes
let n = 9;
 
let tree = new BinaryTree();
 
// Binary tree formation
tree.root = new Node(11);
tree.root.left = new Node(23);
tree.root.right = new Node(44);
tree.root.left.left = new Node(13);
tree.root.left.right = new Node(9);
tree.root.right.left = new Node(22);
tree.root.right.right = new Node(7);
tree.root.right.left.left = new Node(6);
tree.root.right.left.right = new Node(15);
 
//      11
//    /     \
//   23       44
//  /  \     /   \
// 13   9   22     7
//         / \
//        6   15
 
mSum = 0;
 
getSum(tree.root);
 
// Print the sum
document.write(mSum);
 
// This code is contributed by divyeshrabadiya07
 
</script>
Producción: 

33

 

Complejidad de Tiempo: O(N), donde N es el número de Nodes en el Árbol Binario.
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *