Diferencia absoluta máxima entre cualquier suma de dos niveles en un árbol binario

Dado un árbol binario que tiene Nodes positivos y negativos, la tarea es encontrar la máxima diferencia absoluta de la suma de niveles en él.

Ejemplos: 

Input:                     
       4
     /   \
    2    -5
  /  \   / \
-1    3 -2  6
Output: 9
Explanation: 
Sum of all nodes of 0 level is 4
Sum of all nodes of 1 level is -3
Sum of all nodes of 2 level is 6
Hence maximum absolute difference
of level sum = 9 (6 - (-3))

Input: 
        1
      /   \
     2     3
   /  \     \
  4    5     8
            / \
           6   7
Output: 16

Enfoque: para encontrar la diferencia absoluta máxima de la suma de nivel, solo necesitamos encontrar la suma de nivel máximo y la suma de nivel mínimo porque la diferencia absoluta de la suma de nivel máximo y mínimo siempre nos da la diferencia absoluta máxima, es decir

Diferencia absoluta máxima = abs (suma de nivel máximo – suma de nivel mínimo)

 A continuación se muestran los pasos para el algoritmo de la observación anterior: 

  1. La idea es hacer un recorrido por orden de niveles del árbol .
  2. Mientras realiza el recorrido, procese los Nodes de diferentes niveles por separado.
  3. Para cada nivel que se esté procesando, calcule la suma de los Nodes en el nivel y realice un seguimiento de la suma máxima y mínima del nivel.
  4. Luego devuelva la diferencia absoluta de la suma de nivel máximo y mínimo.

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

C++

// C++ program to find the maximum
// absolute difference of level
// sum in Binary Tree
#include <bits/stdc++.h>
using namespace std;
 
// Class containing left and
// right child of current
// node and key value
struct Node
{
    int data;
    Node *left, *right;
};
 
Node *newNode(int data)
{
    Node *node = new Node();
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
 
// Function to find the maximum
// absolute difference of level
// sum in binary tree
// using level order traversal
int maxAbsDiffLevelSum(Node *root)
{
     
    // Initialize value of maximum
    // and minimum level sum
    int maxsum = INT_MIN;
    int minsum = INT_MAX;
     
    queue<Node *> qu;
    qu.push(root);
     
    // Do Level order traversal
    // keeping track of number
    // of nodes at every level.
    while (!qu.empty())
    {
         
        // Get the size of queue when
        // the level order traversal
        // for one level finishes
        int sz = qu.size();
         
        // Iterate for all the nodes in
        // the queue currently
        int sum = 0;
         
        for(int i = 0; i < sz; i++)
        {
             
            // Dequeue an node from queue
            Node *t = qu.front();
            qu.pop();
             
            // Add this node's value to
            // the current sum.
            sum += t->data;
             
            // Enqueue left and
            // right children of
            // dequeued node
            if (t->left != NULL)
                qu.push(t->left);
             
            if (t->right != NULL)
                qu.push(t->right);
        }
         
        // Update the maximum
        // level sum value
        maxsum = max(maxsum, sum);
         
        // Update the minimum
        // level sum value
        minsum = min(minsum, sum);
    }
     
    // return the maximum absolute
    // difference of level sum
    return abs(maxsum - minsum);
}
 
// Driver code
int main()
{
    Node *root = new Node();
     
    root = newNode(4);
    root->left = newNode(2);
    root->right = newNode(-5);
    root->left->left = newNode(-1);
    root->left->right = newNode(3);
    root->right->left = newNode(-2);
    root->right->right = newNode(6);
     
    /*   Constructed Binary tree is:
        4
      /   \
    2      -5
    /  \     / \
    -1    3  -2   6 */
     
    cout << maxAbsDiffLevelSum(root) << endl;
}
 
// This code is contributed by sanjeev2552

Java

// Java program to find the maximum
// absolute difference of level
// sum in Binary Tree
 
import java.util.*;
 
// Class containing left and
// right child of current
// node and key value
class Node {
 
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree {
 
    // Root of the Binary Tree
    Node root;
 
    public BinaryTree()
    {
        root = null;
    }
 
    // Function to find
    // the maximum absolute
    // difference of level
    // sum in binary tree
    // using level order traversal
    public int maxAbsDiffLevelSum()
    {
 
        // Initialize value of maximum
        // and minimum level sum
        int maxsum = Integer.MIN_VALUE;
        int minsum = Integer.MAX_VALUE;
 
        Queue<Node> qu = new LinkedList<>();
        qu.offer(root);
 
        // Do Level order traversal
        // keeping track of number
        // of nodes at every level.
        while (!qu.isEmpty()) {
 
            // Get the size of queue when
            // the level order traversal
            // for one level finishes
            int sz = qu.size();
 
            // Iterate for all the nodes in
            // the queue currently
            int sum = 0;
 
            for (int i = 0; i < sz; i++) {
 
                // Dequeue an node from queue
                Node t = qu.poll();
 
                // Add this node's value to
                // the current sum.
                sum += t.data;
 
                // Enqueue left and
                // right children of
                // dequeued node
                if (t.left != null)
                    qu.offer(t.left);
 
                if (t.right != null)
                    qu.offer(t.right);
            }
 
            // Update the maximum
            // level sum value
            maxsum = Math.max(maxsum, sum);
 
            // Update the minimum
            // level sum value
            minsum = Math.min(minsum, sum);
        }
        // return the maximum absolute
        // difference of level sum
        return Math.abs(maxsum - minsum);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(4);
        tree.root.left = new Node(2);
        tree.root.right = new Node(-5);
        tree.root.left.left = new Node(-1);
        tree.root.left.right = new Node(3);
        tree.root.right.left = new Node(-2);
        tree.root.right.right = new Node(6);
 
        /*   Constructed Binary tree is:
              4
            /   \
          2      -5
        /  \     / \
      -1    3  -2   6 */
 
        System.out.println(
            tree.maxAbsDiffLevelSum());
    }
}

Python3

# Python 3 program to find
# the maximum absolute difference
# of level sum in Binary Tree
 
import sys
# Class containing left and
# right child of current
# node and key value
 
class newNode:
   
    def __init__(self, data):
       
        self.data = data
        self.left = None
        self.right = None
 
# Function to find the maximum
# absolute difference of level
# sum in binary tree
# using level order traversal
def maxAbsDiffLevelSum(root):
 
    # Initialize value of maximum
    # and minimum level sum
    maxsum = -sys.maxsize - 1
    minsum = sys.maxsize
     
    qu = []
    qu.append(root)
     
    # Do Level order traversal
    # keeping track of number
    # of nodes at every level.
    while (len(qu) > 0):
       
        # Get the size of queue when
        # the level order traversal
        # for one level finishes
        sz = len(qu)
         
        # Iterate for all the nodes in
        # the queue currently
        sum = 0
         
        for i in range(sz):
           
            # Dequeue an node from
            # queue
            t = qu[0]
            qu.remove(qu[0])
             
            # Add this node's value
            # to the current sum.
            sum += t.data
             
            # Enqueue left and
            # right children of
            # dequeued node
            if (t.left != None):
                qu.append(t.left)
             
            if (t.right != None):
                qu.append(t.right)
         
        # Update the maximum
        # level sum value
        maxsum = max(maxsum, sum)
         
        # Update the minimum
        # level sum value
        minsum = min(minsum, sum)
     
    # return the maximum absolute
    # difference of level sum
    return abs(maxsum - minsum)
 
# Driver code
if __name__ == '__main__':
   
    root = newNode(4)
    root.left = newNode(2)
    root.right = newNode(-5)
    root.left.left = newNode(-1)
    root.left.right = newNode(3)
    root.right.left = newNode(-2)
    root.right.right = newNode(6)
     
    '''/*   Constructed Binary tree is:
        4
      /   \
    2      -5
    / /     / \
    -1    3  -2   6 */
    '''
     
    print(maxAbsDiffLevelSum(root))
     
# This code is contributed by SURENDRA_GANGWAR

C#

// C# program to find the maximum
// absolute difference of level
// sum in Binary Tree
using System;
using System.Collections.Generic;
 
// Class to represent Tree node
public class Node 
{
    public int data;
    public Node left, right;
     
    public Node(int item) 
    {
        data = item;
        left = null;
        right = null;
    }
}
 
class BinaryTree{
     
Node root;
 
// Function to find the maximum
// absolute difference of level
// sum in binary tree
// using level order traversal
public int maxAbsDiffLevelSum()
{
     
    // Initialize value of maximum
    // and minimum level sum
    int maxsum = Int32.MinValue;
    int minsum = Int32.MaxValue;
 
    Queue<Node> qu = new Queue<Node>();
    qu.Enqueue(root);
 
    // Do Level order traversal
    // keeping track of number
    // of nodes at every level.
    while (qu.Count != 0)
    {
         
        // Get the size of queue when
        // the level order traversal
        // for one level finishes
        int sz = qu.Count;
         
        // Iterate for all the nodes in
        // the queue currently
        int sum = 0;
 
        for(int i = 0; i < sz; i++)
        {
             
            // Dequeue an node from queue
            Node t = qu.Dequeue();
             
            // Add this node's value to
            // the current sum.
            sum += t.data;
             
            // Enqueue left and
            // right children of
            // dequeued node
            if (t.left != null)
                qu.Enqueue(t.left);
 
            if (t.right != null)
                qu.Enqueue(t.right);
        }
         
        // Update the maximum
        // level sum value
        maxsum = Math.Max(maxsum, sum);
 
        // Update the minimum
        // level sum value
        minsum = Math.Min(minsum, sum);
    }
     
    // Return the maximum absolute
    // difference of level sum
    return Math.Abs(maxsum - minsum);
}
 
// Driver code
static public void Main ()
{
    BinaryTree tree = new BinaryTree();
     
    tree.root = new Node(4);
    tree.root.left = new Node(2);
    tree.root.right = new Node(-5);
    tree.root.left.left = new Node(-1);
    tree.root.left.right = new Node(3);
    tree.root.right.left = new Node(-2);
    tree.root.right.right = new Node(6);
     
    /*   Constructed Binary tree is:
          4
        /   \
      2      -5
    /  \     / \
  -1    3  -2   6 */
 
   Console.WriteLine(tree.maxAbsDiffLevelSum());
}
}
 
// This code is contributed by offbeat

Javascript

<script>
    // Javascript program to find the maximum
    // absolute difference of level
    // sum in Binary Tree
     
    // Class to represent Tree node
    class Node
    {
        constructor(item) {
           this.left = null;
           this.right = null;
           this.data = item;
        }
    }
     
    let root;
  
    // Function to find the maximum
    // absolute difference of level
    // sum in binary tree
    // using level order traversal
    function maxAbsDiffLevelSum()
    {
 
        // Initialize value of maximum
        // and minimum level sum
        let maxsum = Number.MIN_VALUE;
        let minsum = Number.MAX_VALUE;
 
        let qu = [];
        qu.push(root);
 
        // Do Level order traversal
        // keeping track of number
        // of nodes at every level.
        while (qu.length != 0)
        {
 
            // Get the size of queue when
            // the level order traversal
            // for one level finishes
            let sz = qu.length;
 
            // Iterate for all the nodes in
            // the queue currently
            let sum = 0;
 
            for(let i = 0; i < sz; i++)
            {
 
                // Dequeue an node from queue
                let t = qu.shift();
 
                // Add this node's value to
                // the current sum.
                sum += t.data;
 
                // Enqueue left and
                // right children of
                // dequeued node
                if (t.left != null)
                    qu.push(t.left);
 
                if (t.right != null)
                    qu.push(t.right);
            }
 
            // Update the maximum
            // level sum value
            maxsum = Math.max(maxsum, sum);
 
            // Update the minimum
            // level sum value
            minsum = Math.min(minsum, sum);
        }
 
        // Return the maximum absolute
        // difference of level sum
        return Math.abs(maxsum - minsum);
    }
    
    root = new Node(4);
    root.left = new Node(2);
    root.right = new Node(-5);
    root.left.left = new Node(-1);
    root.left.right = new Node(3);
    root.right.left = new Node(-2);
    root.right.right = new Node(6);
      
    /*   Constructed Binary tree is:
            4
          /   \
        2      -5
      /  \     / \
    -1    3  -2   6 */
 
      document.write(maxAbsDiffLevelSum());
 
// This code is contributed by divyeshrabadiya07.
</script>
Producción: 

9

 

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

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 *