Dado un árbol binario completo con N niveles numerados [0, (N – 1)] desde la raíz hasta el nivel más bajo en orden decreciente y con pesos numerados entre [1, 2 N – 1] desde la raíz hasta el último Node hoja en el En orden creciente, la tarea de cada Node es ajustar los valores de los niveles de todos los Nodes presentes en su subárbol izquierdo y derecho en función de la siguiente condición:
- Aumenta el nivel de todos los Nodes del subárbol más ligero por la diferencia de sus pesos.
- Disminuya el nivel de todos los Nodes del subárbol más pesado por la diferencia de sus pesos.
Ejemplos:
Aporte:
1 / \ 2 3Salida: 0 0 -2
Explicación:
Los niveles iniciales de los Nodes {1,2,3} son {0,-1,-1} respectivamente.
El Node raíz permanece sin cambios.
El peso del subárbol izquierdo es 2 y el peso del subárbol derecho es 3.
Entonces, el subárbol izquierdo sube por (3 – 2) = 1 nivel a 0.
El subárbol derecho baja por 1 nivel a -2.
Aporte:
1 / \ 2 3 / \ / \ 4 5 6 7Salida: 0 4 -6 4 2 -6 -8
Explicación:
Los niveles iniciales de los Nodes {1,2,3,4,5,6,7} son {0,-1,-1,-2,-2 ,-2,-2} respectivamente.
El Node raíz permanece sin cambios.
El peso del subárbol izquierdo {2,4,5} es 11.
El peso del subárbol derecho {3,6,7} es 16.
Por lo tanto, todos los Nodes del subárbol izquierdo suben 5 mientras que los del subárbol derecho se mueve hacia abajo en 5.
Así, los nuevos niveles de cada Node son:
Node 2: -1 + 5 = 4
Node 3: -1 – 5 = -6
Node 4,5: -2 + 5 = 3
Node 6,7: -2 – 5 = -7
Ahora, los Nodes 4,5 se basan además en la diferencia de sus pesos (5 -4 ) = 1.
Node 4: 3 + 1 = 4
Node 5: 3 – 1 = 2
Del mismo modo, los Nodes 6, 7 también se ajustan.
Node 6: -7 + 1 = -6
Node 7: -7 – 1 = -8
Por lo tanto, los niveles ajustados finales de todos los Nodes son 0 4 -6 4 2 -6 -8.
Enfoque: para resolver este problema, calculamos los pesos de los subárboles izquierdo (w_left) y derecho (w_right) para cada Node y almacenamos su diferencia K . Una vez calculado, aumentamos recursivamente el valor del nivel de todos los Nodes de su subárbol más ligero en K y disminuimos el de su subárbol más pesado en K a partir de sus respectivos valores actuales. Una vez calculados para todos los Nodes, mostramos los valores finales del nivel de cada Node.
El siguiente código es la implementación del enfoque anterior:
C++
// C++ Program to print updated levels
// of each node of a Complete Binary Tree
// based on difference in weights of subtrees
#include <bits/stdc++.h>
using namespace std;
// Node for the given binary tree
struct node {
int weight;
// stores the weight of node
int level;
// stores the level of node
struct node* left;
struct node* right;
node(int w, int l)
{
this->weight = w;
this->level = l;
left = right = NULL;
}
};
// Utility function to insert a node
// in a tree rooted at root
struct node* insert(struct node* root,
int n_weight,
int n_level, queue<node*>& q)
{
struct node* n
= new node(n_weight, n_level);
// if the tree is empty till now
// make node n the root
if (root == NULL)
root = n;
// If the frontmost node of
// queue has no left child
// make node n its left child
// the frontmost node still
// remains in the queue because
// its right child is null yet
else if (q.front()->left == NULL) {
q.front()->left = n;
}
// Make node n the right child of
// the frontmost node and remove
// the front node from queue
else {
q.front()->right = n;
q.pop();
}
// push the node n into queue
q.push(n);
return root;
}
// Function to create a complete binary tree
struct node* createTree(vector<int> weights,
vector<int> levels)
{
// initialise the root node of tree
struct node* root = NULL;
// initialise a queue of nodes
queue<node*> q;
int n = weights.size();
for (int i = 0; i < n; i++) {
/*
keep inserting nodes with weight values
from the weights vector and level values
from the levels vector
*/
root = insert(root, weights[i],
levels[i], q);
}
return root;
}
// Function to print final levels of nodes
void printNodeLevels(struct node* root)
{
if (root == NULL)
return;
queue<node*> q;
q.push(root);
while (!q.empty()) {
cout << q.front()->level << " ";
if (q.front()->left != NULL)
q.push(q.front()->left);
if (q.front()->right != NULL)
q.push(q.front()->right);
q.pop();
}
cout << endl;
}
// Function to find the weight of subtree
int findWeight(struct node* root)
{
// If the root node is null
// then weight of subtree will be 0
if (root == NULL)
return 0;
return root->weight +
findWeight(root->left)
+ findWeight(root->right);
}
// Function to compute new level
// of the nodes based on the
// difference of weight K
void changeLevels(struct node* root, int k)
{
if (root == NULL)
return;
// Change the level of root node
root->level = root->level + k;
// Recursively change the level of
// left and right subtree
changeLevels(root->left, k);
changeLevels(root->right, k);
}
// Function to calculate weight of
// the left and the right subtrees and
// adjust levels based on their difference
void adjustLevels(struct node* root)
{
// No adjustment required
// when root is null
if (root == NULL)
return;
// Find weights of left
// and right subtrees
int w_left = findWeight(root->left);
int w_right = findWeight(root->right);
// find the difference between the
// weights of left and right subtree
int w_diff = w_left - w_right;
// Change the levels of nodes
// according to weight difference at root
changeLevels(root->left, -w_diff);
changeLevels(root->right, w_diff);
// Recursively adjust the levels
// for left and right subtrees
adjustLevels(root->left);
adjustLevels(root->right);
}
// Driver code
int main()
{
// Number of levels
int N = 3;
// Number of nodes
int nodes = pow(2, N) - 1;
vector<int> weights;
// Vector to store weights of tree nodes
for (int i = 1; i <= nodes; i++) {
weights.push_back(i);
}
vector<int> levels;
// Vector to store levels of every nodes
for (int i = 0; i < N; i++) {
// 2^i nodes are present at ith level
for (int j = 0; j < pow(2, i); j++) {
// value of level becomes negative
// while going down the root
levels.push_back(-1 * i);
}
}
// Create tree with the
// given weights and levels
struct node* root
= createTree(weights, levels);
// Adjust the levels
adjustLevels(root);
// Display the final levels
printNodeLevels(root);
return 0;
}
Java
// Java Program to print updated levels
// of each node of a Complete Binary Tree
// based on difference in weights of subtrees
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class GFG {
// Node for the given binary tree
static class node {
int weight;
// stores the weight of node
int level;
// stores the level of node
node left;
node right;
public node(int w, int l)
{
this.weight = w;
this.level = l;
left = right = null;
}
}
// Utility function to insert a node
// in a tree rooted at root
static node insert(node root, int n_weight, int n_level, Queue<node> q)
{
node n = new node(n_weight, n_level);
// if the tree is empty till now
// make node n the root
if (root == null)
root = n;
// If the frontmost node of
// queue has no left child
// make node n its left child
// the frontmost node still
// remains in the queue because
// its right child isnull yet
else if (q.peek().left == null)
{
q.peek().left = n;
}
// Make node n the right child of
// the frontmost node and remove
// the front node from queue
else
{
q.peek().right = n;
q.poll();
}
// push the node n into queue
q.add(n);
return root;
}
// Function to create a complete binary tree
static node createTree(ArrayList<Integer> weights,
ArrayList<Integer> levels)
{
// initialise the root node of tree
node root = null;
// initialise a queue of nodes
Queue<node> q = new LinkedList<>();
int n = weights.size();
for (int i = 0; i < n; i++)
{
/*
* keep inserting nodes with weight values
* from the weights vector and level
* values from the levels vector
*/
root = insert(root, weights.get(i), levels.get(i), q);
}
return root;
}
// Function to print final levels of nodes
static void printNodeLevels(node root)
{
if (root == null)
return;
Queue<node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
System.out.print(q.peek().level + " ");
if (q.peek().left != null)
q.add(q.peek().left);
if (q.peek().right != null)
q.add(q.peek().right);
q.poll();
}
System.out.println();
}
// Function to find the weight of subtree
static int findWeight(node root)
{
// If the root node isnull
// then weight of subtree will be 0
if (root == null)
return 0;
return root.weight + findWeight(root.left) + findWeight(root.right);
}
// Function to compute new level
// of the nodes based on the
// difference of weight K
static void changeLevels(node root, int k)
{
if (root == null)
return;
// Change the level of root node
root.level = root.level + k;
// Recursively change the level of
// left and right subtree
changeLevels(root.left, k);
changeLevels(root.right, k);
}
// Function to calculate weight of
// the left and the right subtrees and
// adjust levels based on their difference
static void adjustLevels(node root)
{
// No adjustment required
// when root isnull
if (root == null)
return;
// Find weights of left
// and right subtrees
int w_left = findWeight(root.left);
int w_right = findWeight(root.right);
// find the difference between the
// weights of left and right subtree
int w_diff = w_left - w_right;
// Change the levels of nodes
// according to weight difference at root
changeLevels(root.left, -w_diff);
changeLevels(root.right, w_diff);
// Recursively adjust the levels
// for left and right subtrees
adjustLevels(root.left);
adjustLevels(root.right);
}
// Driver code
public static void main(String[] args)
{
// Number of levels
int N = 3;
// Number of nodes
int nodes = (int) Math.pow(2, N) - 1;
// Vector to store weights of tree nodes
ArrayList<Integer> weights = new ArrayList<>();
for (int i = 1; i <= nodes; i++) {
weights.add(i);
}
// Vector to store levels of every nodes
ArrayList<Integer> levels = new ArrayList<>();
for (int i = 0; i < N; i++) {
// 2^i nodes are present at ith level
for (int j = 0; j < (int) Math.pow(2, i); j++) {
// value of level becomes negative
// while going down the root
levels.add(-1 * i);
}
}
// Create tree with the
// given weights and levels
node root = createTree(weights, levels);
// Adjust the levels
adjustLevels(root);
// Display the final levels
printNodeLevels(root);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 Program to print # updated levels of each # node of a Complete Binary # Tree based on difference # in weights of subtrees import math # Node for the given binary # tree class node: def __init__(self, w, l): self.weight = w self.level = l self.left = None self.right = None # Utility function to insert # a node in a tree rooted at # root def insert(root, n_weight, n_level, q): n = node(n_weight, n_level); # if the tree is empty # till now make node n # the root if (root == None): root = n; # If the frontmost node of # queue has no left child # make node n its left child # the frontmost node still # remains in the queue because # its right child is null yet elif (q[0].left == None): q[0].left = n; # Make node n the right # child of the frontmost # node and remove the # front node from queue else: q[0].right = n; q.pop(0); # push the node n # into queue q.append(n); return root; # Function to create a # complete binary tree def createTree(weights, levels): # initialise the root # node of tree root = None; # initialise a queue # of nodes q = [] n = len(weights) for i in range(n): ''' keep inserting nodes with weight values from the weights vector and level values from the levels vector ''' root = insert(root, weights[i], levels[i], q); return root; # Function to print final # levels of nodes def printNodeLevels(root): if (root == None): return; q = [] q.append(root); while (len(q) != 0): print(q[0].level, end = ' ') if (q[0].left != None): q.append(q[0].left); if (q[0].right != None): q.append(q[0].right); q.pop(0); print() # Function to find the weight # of subtree def findWeight(root): # If the root node is # null then weight of # subtree will be 0 if (root == None): return 0; return (root.weight + findWeight(root.left) + findWeight(root.right)); # Function to compute new level # of the nodes based on the # difference of weight K def changeLevels(root, k): if (root == None): return; # Change the level of # root node root.level = root.level + k; # Recursively change the # level of left and right # subtree changeLevels(root.left, k); changeLevels(root.right, k); # Function to calculate weight # of the left and the right # subtrees and adjust levels # based on their difference def adjustLevels(root): # No adjustment required # when root is null if (root == None): return; # Find weights of left # and right subtrees w_left = findWeight(root.left); w_right = findWeight(root.right); # find the difference between # the weights of left and # right subtree w_diff = w_left - w_right; # Change the levels of nodes # according to weight difference # at root changeLevels(root.left, -w_diff); changeLevels(root.right, w_diff); # Recursively adjust the levels # for left and right subtrees adjustLevels(root.left); adjustLevels(root.right); # Driver code if __name__=="__main__": # Number of levels N = 3; # Number of nodes nodes = int(math.pow(2, N)) - 1; weights = [] # Vector to store weights # of tree nodes for i in range(1, nodes + 1): weights.append(i); levels = [] # Vector to store levels # of every nodes for i in range(N): # 2^i nodes are present # at ith level for j in range(pow(2, i)): # value of level becomes # negative while going # down the root levels.append(-1 * i); # Create tree with the # given weights and levels root = createTree(weights, levels); # Adjust the levels adjustLevels(root); # Display the final levels printNodeLevels(root); # This code is contributed by Rutvik_56
C#
// C# Program to print updated levels
// of each node of a Complete Binary Tree
// based on difference in weights of subtrees
using System;
using System.Collections.Generic;
class GFG {
// Node for the given binary tree
class node {
public int weight, level;
public node left, right;
public node(int w, int l)
{
this.weight = w;
this.level = l;
left = right = null;
}
}
// Utility function to insert a node
// in a tree rooted at root
static node insert(node root, int n_weight, int n_level, List<node> q)
{
node n = new node(n_weight, n_level);
// if the tree is empty till now
// make node n the root
if (root == null)
root = n;
// If the frontmost node of
// queue has no left child
// make node n its left child
// the frontmost node still
// remains in the queue because
// its right child isnull yet
else if (q[0].left == null)
{
q[0].left = n;
}
// Make node n the right child of
// the frontmost node and remove
// the front node from queue
else
{
q[0].right = n;
q.RemoveAt(0);
}
// push the node n into queue
q.Add(n);
return root;
}
// Function to create a complete binary tree
static node createTree(List<int> weights, List<int> levels)
{
// initialise the root node of tree
node root = null;
// initialise a queue of nodes
List<node> q = new List<node>();
int n = weights.Count;
for (int i = 0; i < n; i++)
{
/*
* keep inserting nodes with weight values
* from the weights vector and level
* values from the levels vector
*/
root = insert(root, weights[i], levels[i], q);
}
return root;
}
// Function to print final levels of nodes
static void printNodeLevels(node root)
{
if (root == null)
return;
List<node> q = new List<node>();
q.Add(root);
while (q.Count > 0) {
Console.Write(q[0].level + " ");
if (q[0].left != null)
q.Add(q[0].left);
if (q[0].right != null)
q.Add(q[0].right);
q.RemoveAt(0);
}
Console.WriteLine();
}
// Function to find the weight of subtree
static int findWeight(node root)
{
// If the root node isnull
// then weight of subtree will be 0
if (root == null)
return 0;
return root.weight + findWeight(root.left) + findWeight(root.right);
}
// Function to compute new level
// of the nodes based on the
// difference of weight K
static void changeLevels(node root, int k)
{
if (root == null)
return;
// Change the level of root node
root.level = root.level + k;
// Recursively change the level of
// left and right subtree
changeLevels(root.left, k);
changeLevels(root.right, k);
}
// Function to calculate weight of
// the left and the right subtrees and
// adjust levels based on their difference
static void adjustLevels(node root)
{
// No adjustment required
// when root isnull
if (root == null)
return;
// Find weights of left
// and right subtrees
int w_left = findWeight(root.left);
int w_right = findWeight(root.right);
// find the difference between the
// weights of left and right subtree
int w_diff = w_left - w_right;
// Change the levels of nodes
// according to weight difference at root
changeLevels(root.left, -w_diff);
changeLevels(root.right, w_diff);
// Recursively adjust the levels
// for left and right subtrees
adjustLevels(root.left);
adjustLevels(root.right);
}
static void Main() {
// Number of levels
int N = 3;
// Number of nodes
int nodes = (int) Math.Pow(2, N) - 1;
// Vector to store weights of tree nodes
List<int> weights = new List<int>();
for (int i = 1; i <= nodes; i++) {
weights.Add(i);
}
// Vector to store levels of every nodes
List<int> levels = new List<int>();
for (int i = 0; i < N; i++) {
// 2^i nodes are present at ith level
for (int j = 0; j < (int) Math.Pow(2, i); j++) {
// value of level becomes negative
// while going down the root
levels.Add(-1 * i);
}
}
// Create tree with the
// given weights and levels
node root = createTree(weights, levels);
// Adjust the levels
adjustLevels(root);
// Display the final levels
printNodeLevels(root);
}
}
// This code is contributed by suresh07.
Javascript
<script>
// JavaScript Program to print updated levels
// of each node of a Complete Binary Tree
// based on difference in weights of subtrees
// Node for the given binary tree
class node {
constructor(w, l) {
this.left = null;
this.right = null;
this.weight = w;
this.level = l;
}
}
// Utility function to insert a node
// in a tree rooted at root
function insert(root, n_weight, n_level, q)
{
let n = new node(n_weight, n_level);
// if the tree is empty till now
// make node n the root
if (root == null)
root = n;
// If the frontmost node of
// queue has no left child
// make node n its left child
// the frontmost node still
// remains in the queue because
// its right child isnull yet
else if (q[0].left == null)
{
q[0].left = n;
}
// Make node n the right child of
// the frontmost node and remove
// the front node from queue
else
{
q[0].right = n;
q.shift();
}
// push the node n into queue
q.push(n);
return root;
}
// Function to create a complete binary tree
function createTree(weights, levels)
{
// initialise the root node of tree
let root = null;
// initialise a queue of nodes
let q = [];
let n = weights.length;
for (let i = 0; i < n; i++)
{
/*
* keep inserting nodes with weight values
* from the weights vector and level
* values from the levels vector
*/
root = insert(root, weights[i], levels[i], q);
}
return root;
}
// Function to print final levels of nodes
function printNodeLevels(root)
{
if (root == null)
return;
let q = [];
q.push(root);
while (q.length > 0) {
document.write(q[0].level + " ");
if (q[0].left != null)
q.push(q[0].left);
if (q[0].right != null)
q.push(q[0].right);
q.shift();
}
document.write("</br>");
}
// Function to find the weight of subtree
function findWeight(root)
{
// If the root node isnull
// then weight of subtree will be 0
if (root == null)
return 0;
return root.weight + findWeight(root.left) +
findWeight(root.right);
}
// Function to compute new level
// of the nodes based on the
// difference of weight K
function changeLevels(root, k)
{
if (root == null)
return;
// Change the level of root node
root.level = root.level + k;
// Recursively change the level of
// left and right subtree
changeLevels(root.left, k);
changeLevels(root.right, k);
}
// Function to calculate weight of
// the left and the right subtrees and
// adjust levels based on their difference
function adjustLevels(root)
{
// No adjustment required
// when root isnull
if (root == null)
return;
// Find weights of left
// and right subtrees
let w_left = findWeight(root.left);
let w_right = findWeight(root.right);
// find the difference between the
// weights of left and right subtree
let w_diff = w_left - w_right;
// Change the levels of nodes
// according to weight difference at root
changeLevels(root.left, -w_diff);
changeLevels(root.right, w_diff);
// Recursively adjust the levels
// for left and right subtrees
adjustLevels(root.left);
adjustLevels(root.right);
}
// Number of levels
let N = 3;
// Number of nodes
let nodes = Math.pow(2, N) - 1;
// Vector to store weights of tree nodes
let weights = [];
for (let i = 1; i <= nodes; i++) {
weights.push(i);
}
// Vector to store levels of every nodes
let levels = [];
for (let i = 0; i < N; i++) {
// 2^i nodes are present at ith level
for (let j = 0; j < Math.pow(2, i); j++) {
// value of level becomes negative
// while going down the root
levels.push(-1 * i);
}
}
// Create tree with the
// given weights and levels
let root = createTree(weights, levels);
// Adjust the levels
adjustLevels(root);
// Display the final levels
printNodeLevels(root);
</script>
Producción:
0 4 -6 4 2 -6 -8
Complejidad de tiempo: O(N), donde N es el número total de Nodes en el árbol.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nishita300601 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA