Suma de todos los Nodes secundarios con valores principales pares en un árbol binario

Dado un árbol binario, la tarea es encontrar la suma de todos los Nodes cuyo padre es par.
Ejemplos: 
 

Input:
       1
      / \
     3   8
        / \
       5   6
      /
     1

Output: 11
The only even nodes are 8 and 6 and 
the sum of their children is 5 + 6 = 11.

Input:
       2
      / \
     3   8
    /   / \
   2   5   6
      /     \
     1       3

Output: 25
3 + 8 + 5 + 6 + 3 = 25

Enfoque: Inicialice sum = 0 y realice un recorrido recursivo del árbol y verifique si el Node es par o no, si el Node es par, agregue los valores de sus hijos a la suma. Finalmente, imprima la suma.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node
struct Node {
    int data;
    struct Node *left, *right;
};
 
// A utility function to allocate a new node
struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return (newNode);
}
 
// This function visit each node in preorder fashion
// And adds the values of the children of a node with
// even value to the res variable
void calcSum(Node* root, int& res)
{
    // Base Case
    if (root == NULL)
        return;
 
    // If the value of the
    // current node if even
    if (root->data % 2 == 0) {
 
        // If the left child of the even
        // node exist then add it to the res
        if (root->left)
            res += root->left->data;
 
        // Do the same with the right child
        if (root->right)
            res += root->right->data;
    }
 
    // Visiting the left subtree and the right
    // subtree just like preorder traversal
    calcSum(root->left, res);
    calcSum(root->right, res);
}
 
// Function to return the sum of nodes
// whose parent has even value
int findSum(Node* root)
{
    // Initialize result
    int res = 0;
 
    calcSum(root, res);
    return res;
}
 
// Driver code
int main()
{
 
    // Creating the tree
    struct Node* root = newNode(2);
    root->left = newNode(3);
    root->right = newNode(8);
    root->left->left = newNode(2);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->left = newNode(1);
    root->right->right->right = newNode(3);
 
    // Print the required sum
    cout << findSum(root);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
// A binary tree node
static class Node
{
    int data;
    Node left, right;
};
static int res;
 
// A utility function to allocate a new node
static Node newNode(int data)
{
    Node newNode = new Node();
    newNode.data = data;
    newNode.left = newNode.right = null;
    return (newNode);
}
 
// This function visit each node in preorder fashion
// And adds the values of the children of a node with
// even value to the res variable
static void calcSum(Node root)
{
    // Base Case
    if (root == null)
        return;
 
    // If the value of the
    // current node if even
    if (root.data % 2 == 0)
    {
 
        // If the left child of the even
        // node exist then add it to the res
        if (root.left != null)
            res += root.left.data;
 
        // Do the same with the right child
        if (root.right != null)
            res += root.right.data;
    }
 
    // Visiting the left subtree and the right
    // subtree just like preorder traversal
    calcSum(root.left);
    calcSum(root.right);
}
 
// Function to return the sum of nodes
// whose parent has even value
static int findSum(Node root)
{
    // Initialize result
    res = 0;
 
    calcSum(root);
    return res;
}
 
// Driver code
public static void main(String[] args)
{
 
    // Creating the tree
    Node root = newNode(2);
    root.left = newNode(3);
    root.right = newNode(8);
    root.left.left = newNode(2);
    root.right.left = newNode(5);
    root.right.right = newNode(6);
    root.right.left.left = newNode(1);
    root.right.right.right = newNode(3);
 
    // Print the required sum
    System.out.print(findSum(root));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach
result = 0;
 
# A binary tree node
class Node :
    def __init__(self,data) :
        self.data = data;
        self.left = None
        self.right = None;
 
# This function visit each node in preorder fashion
# And adds the values of the children of a node with
# even value to the res variable
def calcSum(root, res) :
 
    global result;
     
    # Base Case
    if (root == None) :
        return;
     
    # If the value of the
    # current node if even
    if (root.data % 2 == 0) :
         
        # If the left child of the even
        # node exist then add it to the res
        if (root.left) :
            res += root.left.data;
            result = res;
             
        # Do the same with the right child
        if (root.right) :
            res += root.right.data;
            result = res;
             
    # Visiting the left subtree and the right
    # subtree just like preorder traversal
    calcSum(root.left, res);
    calcSum(root.right, res);
 
# Function to return the sum of nodes
# whose parent has even value
def findSum(root) :
    res = 0;
    calcSum(root, res);
    print(result)
     
# Driver code
if __name__ == "__main__" :
 
    # Creating the tree
    root = Node(2);
    root.left = Node(3);
    root.right = Node(8);
    root.left.left = Node(2);
    root.right.left = Node(5);
    root.right.right = Node(6);
    root.right.left.left = Node(1);
    root.right.right.right = Node(3);
 
    # Print the required sum
    findSum(root);
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// A binary tree node
class Node
{
    public int data;
    public Node left, right;
};
static int res;
 
// A utility function to allocate a new node
static Node newNode(int data)
{
    Node newNode = new Node();
    newNode.data = data;
    newNode.left = newNode.right = null;
    return (newNode);
}
 
// This function visit each node in preorder fashion
// And adds the values of the children of a node with
// even value to the res variable
static void calcSum(Node root)
{
    // Base Case
    if (root == null)
        return;
 
    // If the value of the
    // current node if even
    if (root.data % 2 == 0)
    {
 
        // If the left child of the even
        // node exist then add it to the res
        if (root.left != null)
            res += root.left.data;
 
        // Do the same with the right child
        if (root.right != null)
            res += root.right.data;
    }
 
    // Visiting the left subtree and the right
    // subtree just like preorder traversal
    calcSum(root.left);
    calcSum(root.right);
}
 
// Function to return the sum of nodes
// whose parent has even value
static int findSum(Node root)
{
    // Initialize result
    res = 0;
 
    calcSum(root);
    return res;
}
 
// Driver code
public static void Main(String[] args)
{
 
    // Creating the tree
    Node root = newNode(2);
    root.left = newNode(3);
    root.right = newNode(8);
    root.left.left = newNode(2);
    root.right.left = newNode(5);
    root.right.right = newNode(6);
    root.right.left.left = newNode(1);
    root.right.right.right = newNode(3);
 
    // Print the required sum
    Console.Write(findSum(root));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript implementation of the approach
 
// A binary tree node
class Node
{
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
};
 
var res = 0;
 
// A utility function to allocate a new node
function newNode(data)
{
    var newNode = new Node();
    newNode.data = data;
    newNode.left = newNode.right = null;
    return (newNode);
}
 
// This function visit each node in preorder fashion
// And adds the values of the children of a node with
// even value to the res variable
function calcSum(root)
{
    // Base Case
    if (root == null)
        return;
 
    // If the value of the
    // current node if even
    if (root.data % 2 == 0)
    {
 
        // If the left child of the even
        // node exist then add it to the res
        if (root.left != null)
            res += root.left.data;
 
        // Do the same with the right child
        if (root.right != null)
            res += root.right.data;
    }
 
    // Visiting the left subtree and the right
    // subtree just like preorder traversal
    calcSum(root.left);
    calcSum(root.right);
}
 
// Function to return the sum of nodes
// whose parent has even value
function findSum(root)
{
    // Initialize result
    res = 0;
 
    calcSum(root);
    return res;
}
 
// Driver code
// Creating the tree
var root = newNode(2);
root.left = newNode(3);
root.right = newNode(8);
root.left.left = newNode(2);
root.right.left = newNode(5);
root.right.right = newNode(6);
root.right.left.left = newNode(1);
root.right.right.right = newNode(3);
// Print the required sum
document.write(findSum(root));
 
 
</script>
Producción: 

25

 

Complejidad de tiempo: O(n) donde n es el número de Nodes en el árbol binario dado.
 

Publicación traducida automáticamente

Artículo escrito por mehul_02 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 *