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:
- La idea es hacer un recorrido por orden de niveles del árbol .
- Mientras realiza el recorrido, procese los Nodes de diferentes niveles por separado.
- 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.
- 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)