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)