Minimice la diferencia absoluta entre la suma de los subárboles formados después de dividir el árbol binario en dos

Dado un árbol binario que consta de N Nodes, la tarea es dividir el árbol binario en dos subárboles eliminando un borde de modo que se minimice la diferencia absoluta de la suma de los subárboles.

Ejemplo:

Entrada:      1
               / \
             2 3
           / \ \
         4 5 8
                    / \
                  6 7 
Salida: 6
Explicación: Divide el árbol entre los vértices 3 y 8. Los subárboles creados tienen sumas 21 y 15

Entrada : 1
               / \
             2 3
           / \ / \
        4 5 6 7
                      
Salida : 4
Explicación: Divide el árbol entre los vértices 1 y 3. Los subárboles creados tienen sumas 16 y 12

Enfoque: el problema dado se puede resolver siguiendo los pasos a continuación:

  • Inicialice la variable minDiff al valor máximo de Integer que almacenará la respuesta
  • Use el recorrido posterior al pedido para almacenar la suma del Node actual, el subárbol izquierdo y el subárbol derecho en el Node actual
  • Use el recorrido de preorden y en cada llamada recursiva encuentre la suma de los subárboles si la división es entre:
    • Node actual y Node secundario izquierdo
    • Node actual y Node secundario derecho
  • Actualice minDiff si en cualquier llamada recursiva la diferencia de subárboles es menor que minDiff

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;
 
struct Node {
    Node* left;
    Node* right;
    int val;
  
    Node(int val)
    {
        this->val = val;
        this->left = nullptr;
        this->right = nullptr;
    }
};
 
int postOrder(Node* root)
{
    if (root == nullptr)
        return 0;
    root->val += postOrder(root->left) + postOrder(root->right);
    return root->val;
}
 
void preOrder(Node* root, int minDiff[])
{
    if (root == nullptr)
        return;
 
    // Absolute difference in subtrees
    // if left edge is broken
    int leftDiff = abs(root->left->val - (root->val - root->left->val));
 
    // Absolute difference in subtrees
    // if right edge is broken
    int rightDiff = abs(root->right->val - (root->val - root->right->val));
 
    // Update minDiff if a difference
    // lesser than it is found
    minDiff[0] = min(minDiff[0], min(leftDiff, rightDiff));
 
    return;
}
 
// Function to calculate minimum absolute
// difference of subtrees after
// splitting the tree into two parts
int minAbsDiff(Node* root)
{
 
    // Reference variable
    // to store the answer
    int minDiff[1];
 
    minDiff[0] = INT_MAX;
 
    // Function to store sum of values
    // of current node, left subtree and
    // right subtree in place of
    // current node's value
    postOrder(root);
 
    // Function to perform every
    // possible split and calculate
    // absolute difference of subtrees
    preOrder(root, minDiff);
 
    return minDiff[0];
}
 
int main()
{
    // Construct the tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
 
    // Print the output
    cout << minAbsDiff(root);
 
    return 0;
}
 
// This code is contributed by mukesh07.

Java

// Java implementation for the above approach
import java.lang.Math;
import java.io.*;
 
class GFG {
 
    static class Node {
        Node left, right;
        int val;
        public Node(int val)
        {
            this.val = val;
            this.left = this.right = null;
        }
    }
 
    // Function to calculate minimum absolute
    // difference of subtrees after
    // splitting the tree into two parts
    public static int minAbsDiff(Node root)
    {
 
        // Reference variable
        // to store the answer
        int[] minDiff = new int[1];
 
        minDiff[0] = Integer.MAX_VALUE;
 
        // Function to store sum of values
        // of current node, left subtree and
        // right subtree in place of
        // current node's value
        postOrder(root);
 
        // Function to perform every
        // possible split and calculate
        // absolute difference of subtrees
        preOrder(root, minDiff);
 
        return minDiff[0];
    }
 
    public static int postOrder(Node root)
    {
        if (root == null)
            return 0;
        root.val += postOrder(root.left)
                    + postOrder(root.right);
        return root.val;
    }
 
    public static void preOrder(Node root,
                                int[] minDiff)
    {
        if (root == null)
            return;
 
        // Absolute difference in subtrees
        // if left edge is broken
        int leftDiff
            = Math.abs(root.left.val
                       - (root.val - root.left.val));
 
        // Absolute difference in subtrees
        // if right edge is broken
        int rightDiff
            = Math.abs(root.right.val
                       - (root.val - root.right.val));
 
        // Update minDiff if a difference
        // lesser than it is found
        minDiff[0]
            = Math.min(minDiff[0],
                       Math.min(leftDiff, rightDiff));
 
        return;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Construct the tree
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
 
        // Print the output
        System.out.println(minAbsDiff(root));
    }
}

Python3

# Python3 implementation for the above approach
import sys
 
# Structure of Node
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
# Function to calculate minimum absolute
# difference of subtrees after
# splitting the tree into two parts
def minAbsDiff(root):
   
    # Reference variable
    # to store the answer
    minDiff = [0]*(1)
 
    minDiff[0] = sys.maxsize
 
    # Function to store sum of values
    # of current node, left subtree and
    # right subtree in place of
    # current node's value
    postOrder(root)
 
    # Function to perform every
    # possible split and calculate
    # absolute difference of subtrees
    preOrder(root, minDiff)
 
    return minDiff[0]
 
def postOrder(root):
    if (root == None):
        return 0
    root.val += postOrder(root.left) + postOrder(root.right)
    return root.val
 
def preOrder(root, minDiff):
    if (root == None):
        return
 
    # Absolute difference in subtrees
    # if left edge is broken
    leftDiff = abs(root.left.val - (root.val - root.left.val))
 
    # Absolute difference in subtrees
    # if right edge is broken
    rightDiff = abs(root.right.val - (root.val - root.right.val))
 
    # Update minDiff if a difference
    # lesser than it is found
    minDiff[0] = min(minDiff[0], min(leftDiff, rightDiff))
 
    return
 
# Construct the tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
 
# Print the output
print(minAbsDiff(root))
 
# This code is contributed by rameshtravel07.

C#

// C# implementation for the above approach
using System;
 
public class GFG {
 
    class Node {
        public Node left, right;
        public int val;
    }
 
  static Node newNode(int data)
    {
        Node newNode = new Node();
        newNode.val = data;
        newNode.left= null;
        newNode.right = null;
        return newNode;
    }
 
    // Function to calculate minimum absolute
    // difference of subtrees after
    // splitting the tree into two parts
    static int minAbsDiff(Node root)
    {
 
        // Reference variable
        // to store the answer
        int[] minDiff = new int[1];
 
        minDiff[0] = Int32.MaxValue;
 
        // Function to store sum of values
        // of current node, left subtree and
        // right subtree in place of
        // current node's value
        postOrder(root);
 
        // Function to perform every
        // possible split and calculate
        // absolute difference of subtrees
        preOrder(root, minDiff);
 
        return minDiff[0];
    }
 
   static int postOrder(Node root)
    {
        if (root == null)
            return 0;
        root.val += postOrder(root.left)
                    + postOrder(root.right);
        return root.val;
    }
 
   static void preOrder(Node root,
                                int[] minDiff)
    {
        if (root == null)
            return;
 
        // Absolute difference in subtrees
        // if left edge is broken
        int leftDiff
            = Math.Abs(root.left.val
                       - (root.val - root.left.val));
 
        // Absolute difference in subtrees
        // if right edge is broken
        int rightDiff
            = Math.Abs(root.right.val
                       - (root.val - root.right.val));
 
        // Update minDiff if a difference
        // lesser than it is found
        minDiff[0]
            = Math.Min(minDiff[0],
                       Math.Min(leftDiff, rightDiff));
 
        return;
    }
 
    // Driver code
    public static void Main()
    {
        // Construct the tree
        Node root =  newNode(1);
        root.left =  newNode(2);
        root.right =  newNode(3);
        root.left.left =  newNode(4);
        root.left.right =  newNode(5);
        root.right.left =  newNode(6);
        root.right.right =  newNode(7);
 
        // Print the output
        Console.Write(minAbsDiff(root));
    }
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
    // Javascript implementation for the above approach
     
    // Structure of Node
    class Node
    {
        constructor(val) {
           this.left = null;
           this.right = null;
           this.val = val;
        }
    }
     
    // Function to calculate minimum absolute
    // difference of subtrees after
    // splitting the tree into two parts
    function minAbsDiff(root)
    {
  
        // Reference variable
        // to store the answer
        let minDiff = new Array(1);
  
        minDiff[0] = Number.MAX_VALUE;
  
        // Function to store sum of values
        // of current node, left subtree and
        // right subtree in place of
        // current node's value
        postOrder(root);
  
        // Function to perform every
        // possible split and calculate
        // absolute difference of subtrees
        preOrder(root, minDiff);
  
        return minDiff[0];
    }
  
    function postOrder(root)
    {
        if (root == null)
            return 0;
        root.val += postOrder(root.left)
                    + postOrder(root.right);
        return root.val;
    }
  
    function preOrder(root, minDiff)
    {
        if (root == null)
            return;
  
        // Absolute difference in subtrees
        // if left edge is broken
        let leftDiff
            = Math.abs(root.left.val
                       - (root.val - root.left.val));
  
        // Absolute difference in subtrees
        // if right edge is broken
        let rightDiff
            = Math.abs(root.right.val
                       - (root.val - root.right.val));
  
        // Update minDiff if a difference
        // lesser than it is found
        minDiff[0]
            = Math.min(minDiff[0],
                       Math.min(leftDiff, rightDiff));
  
        return;
    }
     
    // Construct the tree
    let root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
 
    // Print the output
    document.write(minAbsDiff(root));
 
// This code is contributed by decode2207.
</script>
Producción: 

4

 

Complejidad de Tiempo : O(N)  
Espacio Auxiliar : O(1)

Publicación traducida automáticamente

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