Dado un árbol binario , la tarea es encontrar todos los valores mínimos mayores o iguales a cero, que deben sumarse en cada nivel para que la suma en cada nivel sea igual .
Ejemplos:
Entrada:
1
/ \
2 3
/ \
4 5
Salida: 8 4 0
Explicación: La suma inicial en cada nivel es {1, 5, 9}. Para que todos los niveles sumen lo mismo, los valores mínimos que se suman son {8, 4, 0}. Entonces, las sumas finales en cada nivel se convierten en {1 + 8 , 5 + 4 , 9 + 0 }, es decir, {9, 9, 9}.Entrada:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Salida: 16 11 3 0
Enfoque: El problema dado se puede resolver encontrando la suma del nivel máximo en un árbol binario. Mediante el enfoque codicioso , el valor mínimo que debe agregarse en cada nivel debe ser igual a la diferencia entre la suma de ese nivel en el árbol binario con la suma del nivel máximo en un árbol binario.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Node class
class Node {
public:
int data;
Node *left, *right;
Node(int item)
{
data = item;
left = right = NULL;
}
};
// Function to find sum of nodes
// present in a single level.
void Utilfun(Node* root, int level, vector<int>& ans)
{
if (root == NULL) {
return;
}
// Adding the data
// of all the level
if (ans.size() == level) {
ans.push_back(root->data);
}
// If previous node data is already
// then update ans
else {
int val = ans[level] + root->data;
ans[level] = val;
}
// Basic dfs approach to traverse
// on all the nodes with next level
Utilfun(root->left, level + 1, ans);
Utilfun(root->right, level + 1, ans);
}
// Function to find the minimum
// value added to make each level
// sum equal
vector<int>
levelOrderAP(Node* root)
{
// Initialization of array
vector<int> finalAns;
// If root is null
if (root == NULL) {
return finalAns;
}
// Function Call
Utilfun(root, 0, finalAns);
int maxi = INT_MIN;
// finding the maximum element
for (int ele : finalAns) {
maxi = max(maxi, ele);
}
// Subtracting all the elements
// from maximum elements
for (int i = 0; i < finalAns.size(); i++) {
int val = maxi - finalAns[i];
finalAns[i] = val;
}
return finalAns;
}
// Driver Code
int main()
{
Node* root = new Node(8);
root->left = new Node(3);
root->right = new Node(10);
root->left->left = new Node(1);
root->left->right = new Node(6);
root->right->right = new Node(14);
root->left->right->left = new Node(4);
root->left->right->right = new Node(7);
root->right->right->left = new Node(13);
vector<int> ans = levelOrderAP(root);
for (auto i : ans) {
cout << i << " ";
}
return 0;
}
// This code is contributed by maddler.
Java
// Java program for the above approach
import java.util.*;
// Node class
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
// Binary tree class
class BinaryTree {
Node root;
public BinaryTree()
{
root = null;
}
// Function to find the minimum
// value added to make each level
// sum equal
static ArrayList<Integer> levelOrderAP(Node root)
{
// Initialization of array
ArrayList<Integer> finalAns = new ArrayList<>();
// If root is null
if (root == null) {
return finalAns;
}
// Function Call
Utilfun(root, 0, finalAns);
int maxi = Integer.MIN_VALUE;
// finding the maximum element
for (int ele : finalAns) {
maxi = Math.max(maxi, ele);
}
// Subtracting all the elements
// from maximum elements
for (int i = 0; i < finalAns.size(); i++) {
int val = maxi - finalAns.get(i);
finalAns.set(i, val);
}
return finalAns;
}
// Function to find sum of nodes
// present in a single level.
static void Utilfun(Node root,
int level,
ArrayList<Integer> ans)
{
if (root == null) {
return;
}
// Adding the data
// of all the level
if (ans.size() == level) {
ans.add(root.data);
}
// If previous node data is already
// then update ans
else {
int val = ans.get(level)
+ root.data;
ans.set(level, val);
}
// Basic dfs approach to traverse
// on all the nodes with next level
Utilfun(root.left, level + 1, ans);
Utilfun(root.right, level + 1, ans);
}
// Driver Code
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(8);
tree.root.left = new Node(3);
tree.root.right = new Node(10);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(6);
tree.root.right.right = new Node(14);
tree.root.left.right.left = new Node(4);
tree.root.left.right.right = new Node(7);
tree.root.right.right.left = new Node(13);
ArrayList<Integer> ans
= levelOrderAP(tree.root);
System.out.println(ans);
}
}
Python3
# Python3 program for the above approach
import sys
# Structure of Node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def newNode(data):
temp = Node(data)
return temp
# Function to find the minimum
# value added to make each level
# sum equal
def levelOrderAP(root):
# Initialization of array
finalAns = []
# If root is null
if (root == None):
return finalAns
# Function Call
Utilfun(root, 0, finalAns)
maxi = -sys.maxsize
# finding the maximum element
for ele in range(len(finalAns)):
maxi = max(maxi, finalAns[ele])
# Subtracting all the elements
# from maximum elements
for i in range(len(finalAns)):
val = maxi - finalAns[i]
finalAns[i] = val
return finalAns
# Function to find sum of nodes
# present in a single level.
def Utilfun(root, level, ans):
if (root == None):
return
# Adding the data
# of all the level
if (len(ans) == level):
ans.append(root.data)
# If previous node data is already
# then update ans
else:
val = ans[level] + root.data
ans[level] = val
# Basic dfs approach to traverse
# on all the nodes with next level
Utilfun(root.left, level + 1, ans)
Utilfun(root.right, level + 1, ans)
root = newNode(8)
root.left = newNode(3)
root.right = newNode(10)
root.left.left = newNode(1)
root.left.right = newNode(6)
root.right.right = newNode(14)
root.left.right.left = newNode(4)
root.left.right.right = newNode(7)
root.right.right.left = newNode(13)
ans = levelOrderAP(root)
print("[", end="")
for i in range(len(ans) - 1):
print(ans[i], ", ", sep = "", end = "")
print(ans[-1], "]", sep = "")
# This code is contributed by rameshtravel07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
public class Node
{
public int data;
public Node left, right;
};
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to find the minimum
// value added to make each level
// sum equal
static List<int> levelOrderAP(Node root)
{
// Initialization of array
List<int> finalAns = new List<int>();
// If root is null
if (root == null) {
return finalAns;
}
// Function Call
Utilfun(root, 0, finalAns);
int maxi = Int32.MinValue;
// finding the maximum element
foreach (int ele in finalAns) {
maxi = Math.Max(maxi, ele);
}
// Subtracting all the elements
// from maximum elements
for (int i = 0; i < finalAns.Count; i++) {
int val = maxi - finalAns[i];
finalAns[i] = val;
}
return finalAns;
}
// Function to find sum of nodes
// present in a single level.
static void Utilfun(Node root,
int level,
List<int> ans)
{
if (root == null) {
return;
}
// Adding the data
// of all the level
if (ans.Count == level) {
ans.Add(root.data);
}
// If previous node data is already
// then update ans
else {
int val = ans[level]
+ root.data;
ans[level] = val;
}
// Basic dfs approach to traverse
// on all the nodes with next level
Utilfun(root.left, level + 1, ans);
Utilfun(root.right, level + 1, ans);
}
// Driver Code
public static void Main()
{
Node root = newNode(8);
root.left = newNode(3);
root.right = newNode(10);
root.left.left = newNode(1);
root.left.right = newNode(6);
root.right.right = newNode(14);
root.left.right.left = newNode(4);
root.left.right.right = newNode(7);
root.right.right.left = newNode(13);
List<int> ans = levelOrderAP(root);
foreach(int i in ans)
Console.Write(i+ " ");
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// Javascript program for the above approach
class Node
{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function newNode(data)
{
let temp = new Node(data);
return temp;
}
// Function to find the minimum
// value added to make each level
// sum equal
function levelOrderAP(root)
{
// Initialization of array
let finalAns = [];
// If root is null
if (root == null) {
return finalAns;
}
// Function Call
Utilfun(root, 0, finalAns);
let maxi = Number.MIN_VALUE;
// finding the maximum element
for(let ele = 0; ele < finalAns.length; ele++) {
maxi = Math.max(maxi, finalAns[ele]);
}
// Subtracting all the elements
// from maximum elements
for (let i = 0; i < finalAns.length; i++) {
let val = maxi - finalAns[i];
finalAns[i] = val;
}
return finalAns;
}
// Function to find sum of nodes
// present in a single level.
function Utilfun(root, level, ans)
{
if (root == null) {
return;
}
// Adding the data
// of all the level
if (ans.length == level) {
ans.push(root.data);
}
// If previous node data is already
// then update ans
else {
let val = ans[level] + root.data;
ans[level] = val;
}
// Basic dfs approach to traverse
// on all the nodes with next level
Utilfun(root.left, level + 1, ans);
Utilfun(root.right, level + 1, ans);
}
let root = newNode(8);
root.left = newNode(3);
root.right = newNode(10);
root.left.left = newNode(1);
root.left.right = newNode(6);
root.right.right = newNode(14);
root.left.right.left = newNode(4);
root.left.right.right = newNode(7);
root.right.right.left = newNode(13);
let ans = levelOrderAP(root);
document.write("[");
for(let i = 0; i < ans.length - 1; i++)
{
document.write(ans[i] + ", ");
}
document.write(ans[ans.length - 1] + "]");
// This code is contributed by decode2207.
</script>
Producción
[16, 11, 3, 0]
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por priyesh1545 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA