Dado un árbol binario con N Nodes, en el que cada valor de Node representa el número de dulces presentes en ese Node, y hay N dulces en total. En un movimiento, uno puede elegir dos Nodes adyacentes y mover un caramelo de un Node a otro (el movimiento puede ser de padre a hijo o de hijo a padre).
La tarea es encontrar el número de movimientos necesarios para que cada Node tiene exactamente un caramelo.
Ejemplos:
Input : 3
/ \
0 0
Output : 2
Explanation: From the root of the tree, we move one
candy to its left child, and one candy to
its right child.
Input : 0
/ \
3 0
Output :3
Explanation : From the left child of the root, we move
two candies to the root [taking two moves]. Then, we move
one candy from the root of the tree to the right child.
Solución recursiva:
la idea es atravesar el árbol desde la hoja hasta la raíz y equilibrar consecutivamente todos los Nodes. Para equilibrar un Node, la cantidad de dulces en ese Node debe ser 1.
Puede haber dos casos:
- Si un Node necesita caramelos, si el Node del árbol tiene 0 caramelos (un exceso de -1 de lo que necesita), entonces deberíamos empujar un caramelo de su padre al Node.
- Si el Node tiene más de 1 caramelo. Si tiene, digamos, 4 caramelos (un exceso de 3), entonces debemos empujar 3 caramelos del Node a su padre.
Entonces, el número total de movimientos desde esa hoja hacia o desde su padre es exceso = abs(num_candies – 1) .
Una vez que se equilibra un Node, nunca tendremos que volver a considerar este Node en el resto de nuestro cálculo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to distribute candies
// in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Utility function to find the number of
// moves to distribute all of the candies
int distributeCandyUtil(Node* root, int& ans)
{
// Base Case
if (root == NULL)
return 0;
// Traverse left subtree
int l = distributeCandyUtil(root->left, ans);
// Traverse right subtree
int r = distributeCandyUtil(root->right, ans);
// Update number of moves
ans += abs(l) + abs(r);
// Return number of moves to balance
// current node
return root->key + l + r - 1;
}
// Function to find the number of moves to
// distribute all of the candies
int distributeCandy(Node* root)
{
int ans = 0;
distributeCandyUtil(root, ans);
return ans;
}
// Driver program
int main()
{
/* 3
/ \
0 0
Let us create Binary Tree
shown in above example */
Node* root = newNode(3);
root->left = newNode(0);
root->right = newNode(0);
cout << distributeCandy(root);
return 0;
}
Java
// Java program to distribute candies
// in a Binary Tree
class GfG {
// Binary Tree Node
static class Node {
int key;
Node left, right;
}
static int ans = 0;
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = null;
temp.right = null;
return (temp);
}
// Utility function to find the number of
// moves to distribute all of the candies
static int distributeCandyUtil(Node root)
{
// Base Case
if (root == null)
return 0;
// Traverse left subtree
int l = distributeCandyUtil(root.left);
// Traverse right subtree
int r = distributeCandyUtil(root.right);
// Update number of moves
ans += Math.abs(l) + Math.abs(r);
// Return number of moves to balance
// current node
return root.key + l + r - 1;
}
// Function to find the number of moves to
// distribute all of the candies
static int distributeCandy(Node root)
{
distributeCandyUtil(root);
return ans;
}
// Driver program
public static void main(String[] args)
{
/* 3
/ \
0 0
Let us create Binary Tree
shown in above example */
Node root = newNode(3);
root.left = newNode(0);
root.right = newNode(0);
System.out.println(distributeCandy(root));
}
}
// This code is contributed by Prerna Saini.
Python3
# Python3 program to distribute candies # in a Binary Tree # Binary Tree Node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Utility function to create a new node def newNode(key): temp = Node(key) return temp # Utility function to find the number of # moves to distribute all of the candies def distributeCandyUtil( root, ans): # Base Case if (root == None): return 0, ans; # Traverse left subtree l,ans = distributeCandyUtil(root.left, ans); # Traverse right subtree r,ans = distributeCandyUtil(root.right, ans); # Update number of moves ans += abs(l) + abs(r); # Return number of moves to balance # current node return root.key + l + r - 1, ans; # Function to find the number of moves to # distribute all of the candies def distributeCandy(root): ans = 0; tmp, ans = distributeCandyUtil(root, ans); return ans; # Driver program if __name__=='__main__': ''' 3 / \ 0 0 Let us create Binary Tree shown in above example ''' root = newNode(3); root.left = newNode(0); root.right = newNode(0); print(distributeCandy(root)) # This code is contributed by pratham76
C#
// C# program to distribute candies
// in a Binary Tree
using System;
class GFG {
// Binary Tree Node
public class Node {
public int key;
public Node left, right;
}
static int ans = 0;
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = null;
temp.right = null;
return (temp);
}
// Utility function to find the number of
// moves to distribute all of the candies
static int distributeCandyUtil(Node root)
{
// Base Case
if (root == null)
return 0;
// Traverse left subtree
int l = distributeCandyUtil(root.left);
// Traverse right subtree
int r = distributeCandyUtil(root.right);
// Update number of moves
ans += Math.Abs(l) + Math.Abs(r);
// Return number of moves to balance
// current node
return root.key + l + r - 1;
}
// Function to find the number of moves to
// distribute all of the candies
static int distributeCandy(Node root)
{
distributeCandyUtil(root);
return ans;
}
// Driver Code
public static void Main(String[] args)
{
/* 3
/ \
0 0
Let us create Binary Tree
shown in above example */
Node root = newNode(3);
root.left = newNode(0);
root.right = newNode(0);
Console.WriteLine(distributeCandy(root));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to distribute candies in a Binary Tree
// Binary Tree Node
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.key = key;
}
}
let ans = 0;
// Utility function to create a new node
function newNode(key)
{
let temp = new Node(key);
return (temp);
}
// Utility function to find the number of
// moves to distribute all of the candies
function distributeCandyUtil(root)
{
// Base Case
if (root == null)
return 0;
// Traverse left subtree
let l = distributeCandyUtil(root.left);
// Traverse right subtree
let r = distributeCandyUtil(root.right);
// Update number of moves
ans += Math.abs(l) + Math.abs(r);
// Return number of moves to balance
// current node
return root.key + l + r - 1;
}
// Function to find the number of moves to
// distribute all of the candies
function distributeCandy(root)
{
distributeCandyUtil(root);
return ans;
}
/* 3
/ \
0 0
Let us create Binary Tree
shown in above example */
let root = newNode(3);
root.left = newNode(0);
root.right = newNode(0);
document.write(distributeCandy(root));
</script>
Salida :
2
Solución iterativa:
Aproximación: en cada Node, algunos dulces vendrán de la izquierda y van a la derecha o vienen de la derecha y van a la izquierda. En cada caso, los movimientos aumentarán. Entonces, para cada Node contaremos el número de dulces requeridos en el niño derecho y en el niño izquierdo, es decir (número total de Nodes – dulces totales) para cada niño. Es posible que sea menor que 0 , pero en ese caso también contará como movimiento porque los caramelos adicionales también tienen que viajar a través del Node raíz.
A continuación se muestra la implementación del enfoque iterativo:
C++
// C++ program to distribute
// candies in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
int countinchild(Node* root)
{
// as node exists.
if (root == NULL)
return 0;
int numberofnodes = 0; // to count total nodes.
int sum = 0; // to count total candies present.
queue<Node*> q;
q.push(root);
while (q.size() != 0) {
Node* f = q.front();
q.pop();
numberofnodes++;
sum += f->key;
if (f->left)
q.push(f->left);
if (f->right)
q.push(f->right);
}
// as either less than 0 or greater, it will be counted as
// move as explained in the approach.
return abs(numberofnodes - sum);
}
int distributeCandy(Node* root)
{
// moves will count for total no. of moves.
int moves = 0;
// as 0 node and 0 value.
if (root == NULL)
return 0;
// as leaf node don't have to pass any candies.
if (!root->left && !root->right)
return 0;
// queue to iterate on tree .
queue<Node*> q;
q.push(root);
while (q.size() != 0) {
Node* f = q.front();
q.pop();
// total pass from left child
moves += countinchild(f->left);
// total pass from right child
moves += countinchild(f->right);
if (f->left)
q.push(f->left);
if (f->right)
q.push(f->right);
}
return moves;
}
// Driver program
int main()
{
/* 1
/ \
0 2
Let us create Binary Tree
shown in above example */
Node* root = newNode(1);
root->left = newNode(0);
root->right = newNode(2);
cout << distributeCandy(root);
return 0;
}
Java
// Java program to distribute candies in a Binary Tree
import java.util.*;
public class GFG
{
static class Node {
int key;
Node left, right;
Node(int item)
{
key = item;
left = right = null;
}
}
// Root of the Binary Tree
static Node root;
public GFG()
{
root = null;
}
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node(key);
return (temp);
}
static int countinchild(Node root)
{
// as node exists.
if (root == null)
return 0;
int numberofnodes = 0; // to count total nodes.
int sum = 0; // to count total candies present.
Queue<Node> q = new LinkedList<>();
q.add(root);
while (q.size() != 0) {
Node f = (Node)q.peek();
q.remove();
numberofnodes++;
sum += f.key;
if (f.left != null)
q.add(f.left);
if (f.right != null)
q.add(f.right);
}
// as either less than 0 or greater, it will be counted as
// move as explained in the approach.
return Math.abs(numberofnodes - sum);
}
static int distributeCandy(Node root)
{
// moves will count for total no. of moves.
int moves = 0;
// as 0 node and 0 value.
if (root == null)
return 0;
// as leaf node don't have to pass any candies.
if (root.left == null && root.right == null)
return 0;
// queue to iterate on tree .
Queue<Node> q = new LinkedList<>();
q.add(root);
while (q.size() != 0) {
Node f = (Node)q.peek();
q.remove();
// total pass from left child
moves += countinchild(f.left);
// total pass from right child
moves += countinchild(f.right);
if (f.left != null)
q.add(f.left);
if (f.right != null)
q.add(f.right);
}
return moves;
}
public static void main(String[] args) {
/* 1
/ \
0 2
Let us create Binary Tree
shown in above example */
GFG tree = new GFG();
tree.root = newNode(1);
tree.root.left = newNode(0);
tree.root.right = newNode(2);
System.out.println(distributeCandy(tree.root));
}
}
// This code is contributed by divyeshrabadiyaa07.
Python3
# Python3 program to distribute # candies in a Binary Tree # Binary Tree Node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Utility function to create a new node def newNode(key): temp = Node(key) return temp def countinchild(root): # as node exists. if (root == None): return 0; numberofnodes = 0; # to count total nodes. sum = 0; # to count total candies present. q = [] q.append(root); while (len(q) != 0): f = q[0]; q.pop(0); numberofnodes += 1 sum += f.key; if (f.left): q.append(f.left); if (f.right): q.append(f.right); # as either less than 0 or greater, it will be counted as # move as explained in the approach. return abs(numberofnodes - sum); def distributeCandy(root): # moves will count for total no. of moves. moves = 0; # as 0 node and 0 value. if (root == None): return 0; # as leaf node don't have to pass any candies. if (not root.left and not root.right): return 0; # queue to iterate on tree . q = [] q.append(root); while (len(q) != 0): f = q[0]; q.pop(0); # total pass from left child moves += countinchild(f.left); # total pass from right child moves += countinchild(f.right); if (f.left): q.append(f.left); if (f.right): q.append(f.right); return moves; # Driver program if __name__=='__main__': ''' / 1 / \ 0 2 Let us create Binary Tree shown in above example ''' root = newNode(1); root.left = newNode(0); root.right = newNode(2); print(distributeCandy(root)) # This code is contributed by rutvik_56
C#
// C# program to distribute candies in a Binary Tree
using System;
using System.Collections;
using System.Collections.Generic;
class Node {
public int key;
public Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
public class GFG {
// Root of the Binary Tree
Node root;
public GFG()
{
root = null;
}
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node(key);
return (temp);
}
static int countinchild(Node root)
{
// as node exists.
if (root == null)
return 0;
int numberofnodes = 0; // to count total nodes.
int sum = 0; // to count total candies present.
Queue q = new Queue();
q.Enqueue(root);
while (q.Count != 0) {
Node f = (Node)q.Peek();
q.Dequeue();
numberofnodes++;
sum += f.key;
if (f.left != null)
q.Enqueue(f.left);
if (f.right != null)
q.Enqueue(f.right);
}
// as either less than 0 or greater, it will be counted as
// move as explained in the approach.
return Math.Abs(numberofnodes - sum);
}
static int distributeCandy(Node root)
{
// moves will count for total no. of moves.
int moves = 0;
// as 0 node and 0 value.
if (root == null)
return 0;
// as leaf node don't have to pass any candies.
if (root.left == null && root.right == null)
return 0;
// queue to iterate on tree .
Queue q = new Queue();
q.Enqueue(root);
while (q.Count != 0) {
Node f = (Node)q.Peek();
q.Dequeue();
// total pass from left child
moves += countinchild(f.left);
// total pass from right child
moves += countinchild(f.right);
if (f.left != null)
q.Enqueue(f.left);
if (f.right != null)
q.Enqueue(f.right);
}
return moves;
}
static void Main() {
/* 1
/ \
0 2
Let us create Binary Tree
shown in above example */
GFG tree = new GFG();
tree.root = newNode(1);
tree.root.left = newNode(0);
tree.root.right = newNode(2);
Console.Write(distributeCandy(tree.root));
}
}
// This code is contributed by decode2207.
Javascript
<script>
// Javascript program to distribute
// candies in a Binary Tree
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.key = key;
}
}
// Utility function to create a new node
function newNode(key)
{
let temp = new Node(key);
return (temp);
}
function countinchild(root)
{
// as node exists.
if (root == null)
return 0;
let numberofnodes = 0; // to count total nodes.
let sum = 0; // to count total candies present.
let q = [];
q.push(root);
while (q.length != 0) {
let f = q[0];
q.shift();
numberofnodes++;
sum += f.key;
if (f.left)
q.push(f.left);
if (f.right)
q.push(f.right);
}
// as either less than 0 or greater, it will be counted as
// move as explained in the approach.
return Math.abs(numberofnodes - sum);
}
function distributeCandy(root)
{
// moves will count for total no. of moves.
let moves = 0;
// as 0 node and 0 value.
if (root == null)
return 0;
// as leaf node don't have to pass any candies.
if (root.left == null && root.right == null)
return 0;
// queue to iterate on tree .
let q = [];
q.push(root);
while (q.length != 0) {
let f = q[0];
q.shift();
// total pass from left child
moves += countinchild(f.left);
// total pass from right child
moves += countinchild(f.right);
if (f.left)
q.push(f.left);
if (f.right)
q.push(f.right);
}
return moves;
}
/* 1
/ \
0 2
Let us create Binary Tree
shown in above example */
let root = newNode(1);
root.left = newNode(0);
root.right = newNode(2);
document.write(distributeCandy(root));
</script>
Producción
2
Complejidad temporal: O(N*N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por piyush mehra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA