Suma de todas las diferencias padre-hijo en un árbol binario

Dado un árbol binario, encuentre la suma de todas las diferencias padre-hijo para todos los Nodes que no son hojas del árbol binario dado. 
Tenga en cuenta que la diferencia padre-hijo es (valor del Node padre – (suma de los valores del Node hijo)).
Ejemplos: 
 

Input: 
        1
      /   \
     2     3
    / \   / \
   4   5 6   7
          \
           8
Output: -23
1st parent-child difference = 1 -(2 + 3) = -4
2nd parent-child difference = 2 -(4 + 5) = -7
3rd parent-child difference = 3 -(6 + 7) = -10
4th parent-child difference = 6 - 8 = -2
Total sum = -23

Input: 
        1
      /   \
     2     3
      \   /
       5 6
Output: -10

Enfoque ingenuo: la idea es atravesar el árbol de cualquier manera y verificar si el Node es el Node hoja o no. Si el Node no es un Node hoja, agregue (datos del Node: suma de los datos del Node secundario) al resultado.
Enfoque eficiente: en el resultado final, un análisis detallado sugiere que cada Node interno (Nodes que no son ni raíz ni hoja) una vez se trata como un hijo y una vez como padre, por lo que su contribución en el resultado final es cero. Además, la raíz solo se trata como padre una vez y, de manera similar, todos los Nodes hoja se tratan como hijos una vez. Por lo tanto, el resultado final es (valor de la raíz – suma de todos los Nodes hoja) .
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure for a binary tree node
struct Node {
    int data;
    Node *left, *right;
};
 
// Returns a new node
Node* newNode(int data)
{
    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
}
 
// Utility function which calculates
// the sum of all leaf nodes
void leafSumFunc(Node* root, int* leafSum)
{
    if (!root)
        return;
 
    // Add root data to sum if
    // root is a leaf node
    if (!root->left && !root->right)
        *leafSum += root->data;
 
    // Recursively check in the left
    // and the right sub-tree
    leafSumFunc(root->left, leafSum);
    leafSumFunc(root->right, leafSum);
}
 
// Function to return the required result
int sumParentChildDiff(Node* root)
{
 
    // If root is null
    if (!root)
        return 0;
 
    // If only node is the root node
    if (!root->left && !root->right)
        return root->data;
 
    // Find the sum of all the leaf nodes
    int leafSum = 0;
    leafSumFunc(root, &leafSum);
 
    // Root - sum of all the leaf nodes
    return (root->data - leafSum);
}
 
// Driver code
int main()
{
    // Construct binary tree
    Node* root = newNode(1);
    root->left = newNode(2);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right = newNode(3);
    root->right->right = newNode(7);
    root->right->left = newNode(6);
 
    cout << sumParentChildDiff(root);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Structure for a binary tree node
static class Node
{
    int data;
    Node left, right;
};
 
// Returns a new node
static Node newNode(int data)
{
    Node temp = new Node();
    temp.data = data;
    temp.left = temp.right = null;
    return temp;
}
static int leafSum;
 
// Utility function which calculates
// the sum of all leaf nodes
static void leafSumFunc(Node root )
{
    if (root == null)
        return;
 
    // Add root data to sum if
    // root is a leaf node
    if (root.left == null && root.right == null)
        leafSum += root.data;
 
    // Recursively check in the left
    // and the right sub-tree
    leafSumFunc(root.left);
    leafSumFunc(root.right);
}
 
// Function to return the required result
static int sumParentChildDiff(Node root)
{
 
    // If root is null
    if (root == null)
        return 0;
 
    // If only node is the root node
    if (root.left == null && root.right == null)
        return root.data;
 
    // Find the sum of all the leaf nodes
    leafSum = 0;
    leafSumFunc(root);
 
    // Root - sum of all the leaf nodes
    return (root.data - leafSum);
}
 
// Driver code
public static void main(String args[])
{
    // Construct binary tree
    Node root = newNode(1);
    root.left = newNode(2);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right = newNode(3);
    root.right.right = newNode(7);
    root.right.left = newNode(6);
 
    System.out.println( sumParentChildDiff(root));
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
# Structure for a binary tree node
class Node:
     
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Utility function which calculates
# the sum of all leaf nodes
def leafSumFunc(root, leafSum):
 
    if not root:
        return 0
 
    # Add root data to sum
    # if root is a leaf node
    if not root.left and not root.right:
        leafSum += root.data
         
    # Recursively check in the
    # left and the right sub-tree
    leafSum = max(leafSumFunc(root.left,
                              leafSum), leafSum)
    leafSum = max(leafSumFunc(root.right,
                              leafSum), leafSum)
    return leafSum
 
# Function to return the required result
def sumParentChildDiff(root):
 
    # If root is None
    if not root:
        return 0
 
    # If only node is the root node
    if not root.left and not root.right:
        return root.data
 
    # Find the sum of all the leaf nodes
    leafSum = leafSumFunc(root, 0)
 
    # Root - sum of all the leaf nodes
    return root.data - leafSum
 
# Driver code
if __name__ == "__main__":
 
    # Construct binary tree
    root = Node(1)
    root.left = Node(2)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right = Node(3)
    root.right.right = Node(7)
    root.right.left = Node(6)
 
    print(sumParentChildDiff(root))
 
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
     
class GFG
{
 
// Structure for a binary tree node
public class Node
{
    public int data;
    public Node left, right;
};
 
// Returns a new node
static Node newNode(int data)
{
    Node temp = new Node();
    temp.data = data;
    temp.left = temp.right = null;
    return temp;
}
static int leafSum;
 
// Utility function which calculates
// the sum of all leaf nodes
static void leafSumFunc(Node root )
{
    if (root == null)
        return;
 
    // Add root data to sum if
    // root is a leaf node
    if (root.left == null && root.right == null)
        leafSum += root.data;
 
    // Recursively check in the left
    // and the right sub-tree
    leafSumFunc(root.left);
    leafSumFunc(root.right);
}
 
// Function to return the required result
static int sumParentChildDiff(Node root)
{
 
    // If root is null
    if (root == null)
        return 0;
 
    // If only node is the root node
    if (root.left == null && root.right == null)
        return root.data;
 
    // Find the sum of all the leaf nodes
    leafSum = 0;
    leafSumFunc(root);
 
    // Root - sum of all the leaf nodes
    return (root.data - leafSum);
}
 
// Driver code
public static void Main(String []args)
{
    // Construct binary tree
    Node root = newNode(1);
    root.left = newNode(2);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right = newNode(3);
    root.right.right = newNode(7);
    root.right.left = newNode(6);
 
    Console.WriteLine( sumParentChildDiff(root));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
    // JavaScript implementation of the approach
     
    // Structure for a binary tree node
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
     
    // Returns a new node
    function newNode(data)
    {
        let temp = new Node(data);
        return temp;
    }
    let leafSum;
 
    // Utility function which calculates
    // the sum of all leaf nodes
    function leafSumFunc(root)
    {
        if (root == null)
            return;
 
        // Add root data to sum if
        // root is a leaf node
        if (root.left == null && root.right == null)
            leafSum += root.data;
 
        // Recursively check in the left
        // and the right sub-tree
        leafSumFunc(root.left);
        leafSumFunc(root.right);
    }
 
    // Function to return the required result
    function sumParentChildDiff(root)
    {
 
        // If root is null
        if (root == null)
            return 0;
 
        // If only node is the root node
        if (root.left == null && root.right == null)
            return root.data;
 
        // Find the sum of all the leaf nodes
        leafSum = 0;
        leafSumFunc(root);
 
        // Root - sum of all the leaf nodes
        return (root.data - leafSum);
    }
     
    // Construct binary tree
    let root = newNode(1);
    root.left = newNode(2);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right = newNode(3);
    root.right.right = newNode(7);
    root.right.left = newNode(6);
   
    document.write( sumParentChildDiff(root));
     
</script>

-21