Diferencia entre la suma de Nodes con valores pares e impares en un árbol binario

Dado un árbol binario, la tarea es encontrar la diferencia absoluta entre los Nodes con valores pares e impares en un árbol binario.

Ejemplos: 

Input:
      5
    /   \
   2     6
 /  \     \  
1    4     8
    /     / \ 
   3     7   9
Output: 5
Explanation:
Sum of the odd value nodes is:
5 + 1 + 3 + 7 + 9 = 25 
Sum of the even value nodes is:
2 + 6 + 4 + 8 = 20 
Absolute difference = (25 – 20) = 5.

Input:
      4
    /   \
   1     4
 /  \     \  
7    2     6
Output: 8

Enfoque: 
siga los pasos a continuación para resolver el problema:

• Recorra cada Node del árbol y verifique si el valor en ese Node es par o impar .
• Actualice oddSum e evenSum según corresponda después de visitar cada Node.
• Después de completar el recorrido del árbol, imprima la diferencia absoluta entre oddSum y evenSum .

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

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
int oddsum = 0;
int evensum = 0;
int ans = 0;
 
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
struct node* newnode(int data)
{
    node* temp = new node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Function calculate the sum of
// odd and even value node
void OddEvenDifference(struct node*
                           root)
{
    // If root is NULL
    if (root == NULL) {
        return;
    }
    else {
        // Check if current root
        // is odd or even
        if (root->data % 2 == 0) {
            evensum += root->data;
        }
        else {
            oddsum += root->data;
        }
        // Call on the left subtree
        OddEvenDifference(root->left);
 
        // Call on the right subtree
        OddEvenDifference(root->right);
    }
}
 
// Driver Code
int main()
{
    node* root = newnode(5);
    root->left = newnode(2);
    root->right = newnode(6);
    root->left->left = newnode(1);
    root->left->right = newnode(4);
    root->left->right->left
        = newnode(3);
    root->right->right = newnode(8);
    root->right->right->right
        = newnode(9);
    root->right->right->left
        = newnode(7);
 
    OddEvenDifference(root);
 
    cout << abs(oddsum - evensum)
         << endl;
}

// Java implementation of
// the above approach
class GFG{
 
static int oddsum = 0;
static int evensum = 0;
static int ans = 0;
 
static class node
{
    int data;
    node left;
    node right;
};
 
static node newnode(int data)
{
    node temp = new node();
    temp.data = data;
    temp.left = temp.right = null;
    return temp;
}
 
// Function calculate the sum of
// odd and even value node
static void OddEvenDifference(node root)
{
     
    // If root is null
    if (root == null)
    {
        return;
    }
    else
    {
         
        // Check if current root
        // is odd or even
        if (root.data % 2 == 0)
        {
            evensum += root.data;
        }
        else
        {
            oddsum += root.data;
        }
         
        // Call on the left subtree
        OddEvenDifference(root.left);
 
        // Call on the right subtree
        OddEvenDifference(root.right);
    }
}
 
// Driver Code
public static void main(String[] args)
{
    node root = newnode(5);
    root.left = newnode(2);
    root.right = newnode(6);
    root.left.left = newnode(1);
    root.left.right = newnode(4);
    root.left.right.left = newnode(3);
    root.right.right = newnode(8);
    root.right.right.right = newnode(9);
    root.right.right.left = newnode(7);
 
    OddEvenDifference(root);
 
    System.out.print(Math.abs(
        oddsum - evensum) + "\n");
}
}
 
// This code is contributed by amal kumar choubey

# Python3 implementation of
# the above approach
oddsum = 0
evensum = 0
 
class Node:
     
    def __init__(self, data):
         
        self.left = None
        self.right = None
        self.data = data
         
def newnode(data):
 
    temp = Node(data)
     
    return temp
 
# Function calculate the sum of
# odd and even value node
def OddEvenDifference(root):
     
    global evensum, oddsum
     
    # If root is NULL
    if (root == None):
        return
     
    else:
         
        # Check if current root
        # is odd or even
        if (root.data % 2 == 0):
            evensum += root.data
        else:
            oddsum += root.data
         
        # Call on the left subtree
        OddEvenDifference(root.left)
  
        # Call on the right subtree
        OddEvenDifference(root.right)
     
# Driver code
if __name__=="__main__":
     
    root = newnode(5)
    root.left = newnode(2)
    root.right = newnode(6)
    root.left.left = newnode(1)
    root.left.right = newnode(4)
    root.left.right.left= newnode(3)
    root.right.right = newnode(8)
    root.right.right.right= newnode(9)
    root.right.right.left= newnode(7)
  
    OddEvenDifference(root)
     
    print(abs(oddsum - evensum))
     
# This code is contributed by rutvik_56

// C# implementation of
// the above approach
using System;
 
class GFG{
 
static int oddsum = 0;
static int evensum = 0;
//static int ans = 0;
 
class node
{
    public int data;
    public node left;
    public node right;
};
 
static node newnode(int data)
{
    node temp = new node();
    temp.data = data;
    temp.left = temp.right = null;
    return temp;
}
 
// Function calculate the sum of
// odd and even value node
static void OddEvenDifference(node root)
{
     
    // If root is null
    if (root == null)
    {
        return;
    }
    else
    {
         
        // Check if current root
        // is odd or even
        if (root.data % 2 == 0)
        {
            evensum += root.data;
        }
        else
        {
            oddsum += root.data;
        }
         
        // Call on the left subtree
        OddEvenDifference(root.left);
 
        // Call on the right subtree
        OddEvenDifference(root.right);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    node root = newnode(5);
    root.left = newnode(2);
    root.right = newnode(6);
    root.left.left = newnode(1);
    root.left.right = newnode(4);
    root.left.right.left = newnode(3);
    root.right.right = newnode(8);
    root.right.right.right = newnode(9);
    root.right.right.left = newnode(7);
 
    OddEvenDifference(root);
 
    Console.Write(Math.Abs(
        oddsum - evensum) + "\n");
}
}
 
// This code is contributed by amal kumar choubey

<script>
    // Javascript implementation of the above approach
     
    let oddsum = 0;
    let evensum = 0;
    let ans = 0;
 
    class node
    {
        constructor(data) {
           this.data = data;
           this.left = this.right = null;
        }
    }
     
    function newnode(data)
    {
        let temp = new node(data);
        return temp;
    }
 
    // Function calculate the sum of
    // odd and even value node
    function OddEvenDifference(root)
    {
 
        // If root is null
        if (root == null)
        {
            return;
        }
        else
        {
 
            // Check if current root
            // is odd or even
            if (root.data % 2 == 0)
            {
                evensum += root.data;
            }
            else
            {
                oddsum += root.data;
            }
 
            // Call on the left subtree
            OddEvenDifference(root.left);
 
            // Call on the right subtree
            OddEvenDifference(root.right);
        }
    }
     
    let root = newnode(5);
    root.left = newnode(2);
    root.right = newnode(6);
    root.left.left = newnode(1);
    root.left.right = newnode(4);
    root.left.right.left = newnode(3);
    root.right.right = newnode(8);
    root.right.right.right = newnode(9);
    root.right.right.left = newnode(7);
  
    OddEvenDifference(root);
  
    document.write(Math.abs(oddsum - evensum) + "</br>");
 
</script>

5

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)